How to compare two numbers to see which is greater

Question

Comparing two numbers x,y; if x>y I return 1, else return 0. I am trying to do this using only bitwise operators such as >> << ~ ! & | ^ +.

So far I got this:

int greaterThan(int x,int y) {
return ((~(x-y))>>31);
}

So if x-y is negative, the most significant bit would be a 1. So I negate it to get a 0 and shift it so that it returns a 0. If x-y is positive, the most significant bit would be 0. Negate it to get 1 and shift it to return 1. It doesn't seem to work. Am I doing this wrong or missing something?

Answer 1

Your method does not work for several reasons:

• Assuming x and y are signed values, the subtraction could overflow. Not only does this result in undefined behavior according to the C standard, but on typical implementations where overflow wraps, it will give the wrong results. For instance, if x is INT_MIN and y is 1, x-y will yield INT_MAX, which does not have its high bit set.

• If x and y are unsigned values, then x=UINT_MAX and y=0 is an example where you get the wrong answer. You'd have to impose a condition on the values of x and y (for instance, that neither has its high bit set) in order for this test to work.

What it comes down to is that in order to perform comparisons by testing the "high bit", you need one more bit than the number of bits in the values being compared. In assembly language on reasonably-CISC-ish architectures, the carry flag provides this extra bit, and special conditional jump instructions (as well as carry/borrow instructions) are able to read the value of the carry flag. C provides no way to access such a carry flag, however. One alternate approach might be to use a larger integer type (like long long) so that you can get an extra bit in your result. Good compilers will translate this to a read of the carry flag, rather than actually performing larger arithmetic operations.

Answer 2

C Standard (1999), chapter 6.5.7 Bitwise shift operators, paragraph 5:

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2 . If E1 has a signed type and a negative value, the resulting value is implementation-defined.

I.e., the result for a bit-shift-right on negative numbers is implementation-defined. One possibility is that the "sign bit" gets copied into the bits to the right, which is what GCC seems to do (as it results in all bits set, -1).

Answer 3

@Dan, can you please clarify your question in first post, i.e. what exactly you can use and what you can't use (in your comments you mentioned that you can't use if/else etc.).

Anyway, if you want to get rid of unexpected -1, you should consider casting your value to unsigned int before shifting. This will not make your solution entirely correct though. Try to think about checking numbers' sign bit (e.g. if first bit of x is 0 and first bit of y is 1 then you can be sure that x>y).