Warum funktioniert diese Größer-als-Funktion?

Question

Ich arbeite an einer Hausaufgabe, wo wir eine Funktion namens isGreater (x, y) machen sollen, die zurückgibt, wenn x größer als y ist, aber wir können nur bitweise Operatoren zusammen mit + und! Ich habe das Problem bereits gelöst, indem ich die Regel verwende, wenn x und y unterschiedliche Vorzeichen haben, dann x> = 0 und y < 0 oder wenn x und y das gleiche Vorzeichen haben, dann nur dann, wenn y-x negativ ist.

Als ich jedoch sah, wie andere Leute es lösten, bemerkte ich die folgende Methode, die aus irgendeinem Grund richtig funktioniert.

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

Ich kann nicht für das Leben von mir verstehen, warum das funktioniert, ich meine, das hat etwas mit dem ersten Bit in x zu tun, die nicht in y oder etwas gesetzt?

Hinweis: Scheinbar ist dies nur eine gültige Lösung, wenn x und y int sind, nicht vorzeichenlos int.

Answer 1

31 bedeutet, dass wir nur an dem Zeichen interessiert sind. Wenn ((x & y) + ((x^y) >> 1))> 0 dann x> ~ y.
x & ~ y erzeugt eine Zahl, in der das MSB das erste Bit ist, in dem x ein gesetztes Bit und y eine 0 hat. X^~ y erzeugt eine Zahl, wobei die nicht gesetzten Bits die Bits x und y darstellen abweichen. Wenn wir es um eins verschieben, brauchen wir, dass ihre Summe positiv wird. Dies geschieht nur dann, wenn das erste von Null verschiedene Bit von x & y (also das erste Bit, in dem x gesetzt ist und x und y verschieden sind) mit einem gesetzten Bit in ((x^y) >> 1) übereinstimmt (was die erste bedeutet) Bit, das in einem gesetzt ist, aber nicht in dem anderen gesetzt ist.
Und wenn das höchste Bit in x gesetzt ist, aber nicht in y gesetzt ist, ist auch das höchste Bit in einem gesetzt, aber nicht in dem anderen gesetzt - das bedeutet x ist größer als y.

Beispiel:

(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 

Aus diesem Grund ist es Arbeit BTW für unsigned does't (kein Zeichen gibt).