CODEWITHSUNDEEP
clogicbit-manipulation
jamiees2
jamiees2

Reputation: 176

Why does this greater than function work?

I am working on a homework assignment where we are supposed to make a function called isGreater(x,y) which returns if x is larger than y, but we can only use bitwise operators along with + and !. I have already solved the problem, using the rule if x and y have different signs, then x >= 0 and y < 0 or if x and y have the same sign then only if y-x is negative.

However, when i was looking around how other people solved it, i noticed the following method which works correctly for whatever reason.

y = ~y;   
return !(((x&y) + ((x^y) >> 1)) >> 31);

I cannot for the life of me understand why this works, i figure this has something to do with the first bit in x that isn't set in y or something?

Note: Apparently this is only a valid solution if x and y are ints, not unsigned int.

Upvotes: 6

Views: 317

Answers (1)

kipodi
kipodi

Reputation: 409

31 means we are only interested in the sign. If ((x&y) + ((x^y) >> 1)) > 0 then x > ~y.
x & ~y will produce a number where the MSB will be the first bit where x has a set bit and y has a 0. x^~y will produce a number where the unset bits will represent the bits where x and y differ. If we shift it right by one we need for their sum to become positive. Which will happen only if the first nonzero bit of of x&y (meaning the first bit where x is set and x and y are different) meets with a set bit in ((x^y) >> 1) (meaning the first bit that is set in one but not set in the other).
And if the highest bit is set in x but not set in y, is also the highest bit set in one but not set in the other - this means x is bigger than y.

Example:

(shft is x^~y >> 1, res is shft + x&~y)

x:   000110
y:   001010
~y:  110101
x&~y:000100
x^~y:110011
shft:111001
res: 111101 -> negative

x:   000110
y:   000010
~y:  111101
x&~y:000100
x^~y:111011
shft:111101
res: 000001 -> positive

This is why it does't work for unsigned BTW (no sign there).

Upvotes: 5

Related Questions