Why does this work more than a function?

Question

I am working on homework where we need to create a function called isGreater (x, y) that returns if x is greater than y, but we can only use bitwise operators along with + and !. I 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 yx is negative.

However, when I watched other people solve this, I noticed the following method, which works for some reason.

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

I can’t let my life understand why this works, I suppose this has to do with the first bit in x, which is not set to y or something like that?

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

Answer 1

31 means that we are only interested in the sign. If ((x & y) + ((x ^ y) → 1))> 0, then x> ~ y.
x and ~ y will produce a number, where the MSB will be the first bit, where x has a set bit and y has 0. x ^ ~ y will produce a number in which unsaved bits will represent bits where x and y are different. If we shift it by one, we need their sum to become positive. This will only happen if the first non-zero bit x & y (which means that the first bit, where x is set, and x and y are different) is encountered with the set bit in ((x ^ y) → 1) (which means the first bit that is set to one but not set to another).
And if the most significant bit is set to x, but not set to y, is also the highest bit set in one but not set in the other - this means that x is greater 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 

That is why it does not work for unsigned BTW (there is no mark there).