Perché funziona più in alto della funzione?

Question

Sto lavorando ad un compito a casa dove dovremmo fare una funzione chiamata isGreater (x, y) che restituisce se x è più grande di y, ma possiamo usare solo operatori bitwise insieme a + e!. Ho già risolto il problema, usando la regola se x e y hanno segni diversi, quindi x> = 0 e y < 0 o se x e y hanno lo stesso segno allora solo se y-x è negativo.

Tuttavia, quando mi sono guardato intorno come gli altri lo hanno risolto, ho notato il seguente metodo che funziona correttamente per qualsiasi motivo.

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

non posso per la vita di me capire perché questo funziona, immagino che questo ha qualcosa a che fare con il primo bit x che non è impostato in Y o qualcosa del genere?

Nota: Apparentemente questa è solo una soluzione valida se x e y sono int, non int unsigned.

Answer 1

31 significa che siamo interessati solo al segno. Se ((x & y) + ((x^y) >> 1))> 0 allora x> ~ y.
x & ~ & ~ y produce un numero in cui l'MSB sarà il primo bit dove x ha un bit impostato e y ha uno 0. x^~ y produrrà un numero in cui i bit non impostati rappresenteranno i bit in cui x e y differire. Se lo spostiamo a destra di uno abbiamo bisogno che la loro somma diventi positiva. Che succederà solo se il primo bit non zero di x & y (che indica il primo bit in cui x è impostato e xey sono diversi) si incontra con un bit impostato in ((x^y) >> 1) (che significa il primo bit che è impostato in uno ma non impostato nell'altro).
E se il bit più alto è impostato in x ma non impostato in y, è anche il bit più alto impostato in uno ma non impostato nell'altro - questo significa che x è più grande di y.

Esempio:

(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 

Questo è il motivo per cui does't lavoro per unsigned BTW (nessun segno lì).