Dlaczego ta większa niż funkcja działa?

Question

Pracuję nad zadaniem domowym, w którym mamy wykonać funkcję o nazwie isGreater (x, y), która zwraca, jeśli x jest większe od y, ale możemy używać tylko operatorów bitowych razem z + i!. Rozwiązałem już problem, stosując regułę, jeśli x i y mają różne znaki, to x> = 0 i y < 0 lub jeśli x i y mają ten sam znak wtedy tylko wtedy, gdy y-x jest ujemne.

Jednak gdy rozglądałem się, jak inni rozwiązali to, zauważyłem następującą metodę, która działa poprawnie z jakiegokolwiek powodu.

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

nie mogę dla życia mnie zrozumieć, dlaczego to działa, ja figura to ma coś wspólnego z pierwszego bitu w X, który nie mieści się w y albo coś?

Uwaga: Wygląda na to, że jest to poprawne rozwiązanie tylko wtedy, gdy x i y to ints, a nie unsigned int.

Answer 1

31 oznacza, że ​​jesteśmy zainteresowani tylko znakiem. Jeśli ((x & y) + ((x^y) >> 1))> 0 to x> ~ y.
x & ~ y spowoduje utworzenie liczby, w której MSB będzie pierwszym bitem, gdzie x ma ustawiony bit, a y ma 0. x^~ y spowoduje utworzenie liczby, w której niepasujące bity będą reprezentować bity, w których x i y różnić się. Jeśli przesuniemy to prawo o jeden, potrzebujemy, aby ich suma stała się dodatnia. Co stanie się tylko wtedy, gdy pierwszy niezerowy bit x & y (oznaczający pierwszy bit gdzie x jest ustawiony, a xiy są różne) spotyka się z ustawionym bitem w ((x^y) >> 1) (co oznacza pierwszy bit ustawiony w jednym, ale nie ustawiony w drugim).
A jeśli najwyższy bit jest ustawiony w x, ale nie jest ustawiony w y, jest także najwyższym bitem ustawionym w jednym, ale nie ustawionym w drugim - oznacza to, że x jest większe niż y.

Przykład:

(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 

Dlatego does't pracy dla unsigned BTW (żadnego znaku tam).