comparsion function

[edijs.vee]

okay, this might seem dumb, but I'll ask anyways:

how can I check what's the releation of two numbers, ie whether a>b or b>a or a==b without using comparsion operators and any branching constructions (namely if).

[TheCPUWizard]

You basically can't without resorting to some really obtuse code. So the question is WHY??????

[edijs.vee]

I had this exercise in a test and couldn't get past it. I did everything else, but just couldn't figure this one out. all I did was end up with more and more complex calculations and tricks which ended up in having the need for at least 1 < or > or if... or <>

and everyone I asked didn't do it either.

the code can be as obtuse as needed, it should just do the trick. no beautifullnes required here!

[TheCPUWizard]

OK

any branching constructions (namely if).

If this means you simply cant use an "if" there are ways. If you mean no conditional branching at the machine level, it is nearly impossible.

So which is it?

[edijs.vee]

simply can't use an "if". conditions at the machine level are certainly okay

[TheCPUWizard]

trivial then:

(a==b) ? { //code for == } : ((a-b)/abs(a-b)) ? { code for a<b } : { code for a> b}

[edijs.vee]

okay, thanks! but could you translate that into a c++ function?

like

int compare(int a, int b){

...code...

return result.
}

[ne0n82]

yep its the conditional operator its the same as an if statement

n = x > y ? x : y;

is the same as...

if (x > y)
n = x;
else
n = y;

[TheCPUWizard]

yep its the conditional operator its the same as an if statement

n = x > y ? x : y;

is the same as...

if (x > y)
n = x;
else
n = y;

But you used a relational operator which is illegal.

To get the OP answer...

return (a==b) ? 0 : ((a-b)/abs(a-b)) ? -1  : 1;

[Synthetic Being]

The ternary conditional operator is technically a branching construct provided the compiler can't/isn't allowed to use any branch replacement instructions. By using these, the compiler can completely eliminate simple branching constructs. For x86, the most useful instruction is CMOV, which requires Pentium Pro, Pentium II, AMD Athlon or later to run. For backwards compatibility, this isn't usually enabled by default.

As for the question:

a > b
Evaluate (b - a). If the result is negative, the comparison is true.

a == b
Evaluate (a - b) | (b - a). If the result is negative, the comparison is false.

This function returns parameter 'p' for nonnegative compare and 'n' for negative.

#include <climits>
const unsigned int INT_BITS = CHAR_BIT * sizeof(int);

int conditOper(const int compare, const int p, const int n) {
	return p + ((n - p) & (compare >> (INT_BITS - 1)));
}

This is a practical, fast solution based on number signedness.

[AlbertGM]

return (a==b) ? 0 : ((a-b)/abs(a-b)) ? -1  : 1;

Sorry but I don't understand your answer. This expression will never return 1!! Only can return -1 or 0.
To return 1, (a-b)/abs(a-b) must be 0. That's impossible!!! The previous condition would have been true. So, (a-b)/abs(a-b) must be 1 ó -1, and both are true!!!

Albert.

[jwbarton]

The method posted by Synthetic Being is the closest to what was asked for by the original poster - it doesn't use comparison operators.

This method works ok as long as the 2 numbers being compared are within INT_MAX of each other. It will give incorrect results when the subtraction overflows.

If the overflow detection is important, the following will work:

#include <climits>

const unsigned int INT_BITS = CHAR_BIT * sizeof(int);

int SignBit( const int value )
{
   return static_cast<unsigned int>(value) >> (INT_BITS - 1);
}

int CompareWithOverflow( int first, int second )
{
   return (SignBit(second) - SignBit(first)) +
          (SignBit(first) ^ SignBit(second) ^ 1) * (SignBit(second-first) - SignBit(first-second));
}

Note: I am basing this on the original code by Synthetic Being (checking the sign bits), and then extending it to check for sign differences between the original numbers.

The routine CompareWithOverflow will return -1 if first is less than second, 0 if they are equal, and 1 if first is greater than second. No comparison operators are used.

[googler]

The most significant bit acts as a sign bit in 2's complement and sign-magnitude representation. C++ also allows 1's complement, in which the sign test is different.