this is how you can get minimum or maximum of two numbers without using conditional jumps.

pseudo code:

min(a,b):=((a+b)-abs(a-b))/2;

max(a,b):=((a+b)+abs(a-b))/2;
Posted on 2003-11-26 03:24:17 by babazaga
As a matter of fact, abs() in your pseudo code may include Jcc.

P6 and later has CMOVcc, which makes it much easier and shorter to implement. P5 or earlier can use already-known technique using CDQ (or equivalent sequence of instructions), which can be done with 5 or less instructions. :) For example code, see Intel's optimization manual.
Posted on 2003-11-26 03:59:08 by Starless
Faithful to the proposed pseudo code:
; eax = A

; ecx = B

sub eax, ecx ; eax = A - B
lea ecx, [eax + ecx*2] ; ecx = (A - B) + 2B = A + B
cdq
xor eax, edx ; "conditionally" not eax, on sign
sub eax, edx ; "conditionally" inc eax, on sign
; eax = ABS(A - B)
neg eax ; Remove this line for MAX
add eax, ecx
shr eax, 1


A different method:
; eax = A

; ecx = B

cmp eax, ecx
sbb edx, edx
and eax, edx ; and ecx, edx for max
not edx
and ecx, edx ; and eax, edx for max
or eax, ecx


Mirno
Posted on 2003-11-26 15:36:40 by Mirno
Here's yet another way:


; eax = a, ebx = b

mov edx, ebx
sub edx, eax
sbb ecx, ecx
and ecx, edx

add eax, ecx ; eax = min(a,b)
sub ebx, ecx ; ebx = max(a,b)


At the end of the execution, eax will hold the minimum and ebx will hold the maximum.

Spara
Posted on 2005-01-25 14:35:40 by Sparafusile
babazaga,
Before anyone can provide meaningful answers, you have to specify whether the two numbers are signed or unsigned. Specifying the size of the comparison such as BYTE, WORD, or DWORD also helps in coding the algorithm. Ratch
Posted on 2005-01-28 20:10:35 by Ratch
I recently wrote a couple of small inline functions to do min and max for 2 DWORDS. Each returns the Min and Max respectively



__inline DWORD Min(DWORD dwA, DWORD dwB)
{
__asm
{
mov eax, dwA
cmp eax, dwB
cmovg eax, nB
}
}

__inline DWORD Max(DWORD dwA, DWORD dwB)
{
__asm
{
mov eax, dwA
cmp eax, dwB
cmovl eax, nB
}
}


Return values are always EAX so there you have it.. Min or Max in 3 instructions with no jumps!

Phred
Posted on 2005-02-03 09:16:34 by Phred
Phred, 2 dwords or 2 signed dwords?

cmova
cmovb
Posted on 2005-02-03 13:28:30 by drizz
Thank you Drizz - my bad.

As Drizz pointed out.... cmovg and cmovl (conditional move if greater and less than) is for signed numbers where as cmova and cmovb are for unsigned numbers.

lets try that again....



// this is the UNSIGNED version
__inline DWORD Min(DWORD dwA, DWORD dwB)
{
__asm
{
mov eax, dwA
cmp eax, dwB
cmova eax, nB
}
}

__inline DWORD Max(DWORD dwA, DWORD dwB)
{
__asm
{
mov eax, dwA
cmp eax, dwB
cmovb eax, nB
}
}

// this is the SIGNED version
__inline int Min(int dwA, int dwB)
{
__asm
{
mov eax, dwA
cmp eax, dwB
cmovg eax, nB
}
}

__inline int Max(int dwA, int dwB)
{
__asm
{
mov eax, dwA
cmp eax, dwB
cmovl eax, nB
}
}
Posted on 2005-02-03 13:43:58 by Phred
Thats a Fantastic logic. Thanks a million geniuses
Posted on 2005-02-19 00:05:31 by jay_javin
The last code will give errors if compiled but this one is very nice a clean now. If you use this in Visual C++ 6.0, the compiler will complain that none of the functions have return statments in them BUT in reality, EAX is the return value used so I have included the #pragma's to disable the warning messages.



#pragma warning( disable : 4035)

// this is the UNSIGNED version
__inline DWORD Min(DWORD dwA, DWORD dwB)
{
__asm
{
mov eax, dwA
cmp eax, dwB
cmova eax, dwB
}
}

__inline DWORD Max(DWORD dwA, DWORD dwB)
{
__asm
{
mov eax, dwA
cmp eax, dwB
cmovb eax, dwB
}
}

// this is the SIGNED version
__inline int Min(int nA, int nB)
{
__asm
{
mov eax, nA
cmp eax, nB
cmovg eax, nB
}
}

__inline int Max(int nA, int nB)
{
__asm
{
mov eax, nA
cmp eax, nB
cmovl eax, nB
}
}

#pragma warning( default : 4035 )


Ok be good!
Posted on 2005-02-22 11:43:00 by Phred
cmov* instructions are not completely compatiable, plus they take up at least one extra byte, and most likely more clock time (as i haven't checked, but assuming it's an extended instruction - 0x0f ...)
Posted on 2005-02-22 21:30:55 by Drocon
By not compatible you mean like some AMD processors don't support them?

While it is an extended instruction, I would still take the extra byte and possibly more clock time over using branches considering a regular Min/Max in Visual C++ compiles to several memory reads, 12 instructions and 2 branches :)

I'm wondering what are some other branchless ways of determining min/max of 2 values? You could very well do it with MMX but for one set of values only but I prefer to use MMX when I group stuff together.
Posted on 2005-02-24 11:35:51 by Phred