为什么这个功能比功能更好？

Question

我正在做一个家庭作业，我们应该做一个叫做isGreater（x，y）的函数，如果x大于y，它会返回，但是我们只能和+和！一起使用按位运算符。我已经解决了这个问题，如果x和y具有不同的符号，则使用规则，那么x> = 0和y < 0或者如果x和y具有相同的符号，那么只有y-x为负数。

但是，当我在寻找其他人如何解决它时，我注意到以下方法，无论出于何种原因都能正确工作。

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

我不能为我的生命明白为什么这个工程，我想这已经是与X中的第一位未在Y或设置的东西？

注意：显然这只是一个有效的解决方案，如果x和y是int，而不是unsigned int。

Answer 1

31表示我们只对标志感兴趣。如果（（x & y）+（（x^y）>> 1））> 0，则x>〜y。
x & y将产生一个数字，其中MSB将是第一个位，其中x具有一个设定位并且y具有0.x^_y将产生一个数字，其中未设定位将表示其中x和y不同。如果我们正确地将它移向正确的话，我们需要它们的总和。只有当x（x，y）>> 1）中的第一个非零位（意味着x被设置且x和y不同的第一个位）与（（x^y）>> 1）中的设置位相符（这意味着第一个位设置在一个中，但未设置在另一个中）。
如果最高位设置在x中，但未设置在y中，也是在一个中设置的最高位，而另一个中未设置 - 这意味着x大于y。

例子：

(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 

这就是为什么它简化版，无符号的工作BTW（无需登录那里）。