大于C的function
我知道这是一个古老的问题，你可能也遇到过这个问题，但我的解决方案中有一个错误，我不知道如何解决它。 我需要编写一个比较两个整数的函数。 我只允许使用操作（！，〜，＆，^，|，+，>>，<<），也没有控制结构（if，else循环等）。
isGreater(int x, int y) { //returns 1 if x > y. return ((y+(~x+1))>>31)&1; } 我的想法很简单，我们计算yx，我们移动31得到符号位，如果它是负数，那么我们返回零，否则我们返回1.当x为负时，失败并且当falsly返回1时失败，尽管它应返回零。 我被困在这里，不知道如何继续。
我们假设整数是32位并使用二进制补码表示。 这个问题与可移植性无关。 一些帮助将非常感激。
提前致谢
Hacker’s Delight有一章比较谓词，这正是我们在这里所需要的。
它写的一件事是：
x < y: (x - y) ^ ((x ^ y) & ((x - y) ^ x))
我们几乎可以直接使用，除了应该交换x和y之外，减法必须用合法的东西代替，结果出现在最高位而不是最低位。 幸运的是a - b == ~(~a + b)因此不太难。 首先应用这些转换：
// swap x <-> y (y - x) ^ ((y ^ x) & ((y - x) ^ y)) // rewrite subtraction ~(~y + x) ^ ((y ^ x) & (~(~y + x) ^ y)) // get answer in lsb ((~(~y + x) ^ ((y ^ x) & (~(~y + x) ^ y))) >> 31) & 1
我这里有一个网站说它有效。
如果允许局部变量，可以通过分解子表达式来简化一点
~(~y + x) ：
int diff = ~(~y + x); return ((diff ^ ((y ^ x) & (diff ^ y))) >> 31) & 1;
首先让我们澄清一下我们假设：
- 负整数用2的补码表示
-
int正好是32位宽，long long正好是64位宽 - 右移一个负数是算术移位
解决方案中的(~x+1)部分存在问题，该部分应返回-x 。 问题是INT_MIN的绝对值大于INT_MIN的绝对值，因此当x为INT_MIN (~x+1)产生INT_MIN而不是预期的-INT_MIN 。
在解决方案的y+(-x)部分也存在溢出问题（第二步）。
现在，如果允许使用除int之外的其他类型，我们可以通过在转换之前将值转换为long long来解决这两个问题，假设它是64位类型，这样(~x+1)将返回预期的结果-x和y+(-x)不会导致任何溢出。 那么，显然，我们必须将>>31位更改为>>63 。
最终解决方案如下：
static bool isGreater(int x, int y) { long long llx = x; long long lly = y; long long result = ((lly+(~llx+1))>>63)&1; return result; }
用一些角点测试它是可行的，例如x == INT_MIN ， x == 0和x == INT_MAX ：
int main(void) { int x = INT_MIN; for (long long y = INT_MIN; y <= INT_MAX; ++y) { assert(isGreater(x, y) == (x > y)); } x = INT_MAX; for (long long y = INT_MIN; y <= INT_MAX; ++y) { assert(isGreater(x, y) == (x > y)); } x = 0; for (long long y = INT_MIN; y <= INT_MAX; ++y) { assert(isGreater(x, y) == (x > y)); } }
这在我的特定机器上使用我的特定编译器是成功的。 测试耗时163秒。
但同样，这取决于能否使用除int之外的其他类型（但是再次使用更多的工作，您可以使用int模拟long long ）。
如果您使用int32_t和int64_t而不是int和long long ，那么整个事情可以更加可移植。 但是，它仍然不可移植：
ISO / IEC 9899：2011§6.5.7按位移位算子
5 E1 >> E2的结果右移E2位位置。 如果E1具有无符号类型或者E1具有有符号类型和非负值，则结果的值是E1 / 2E2的商的整数部分。 如果E1具有带符号类型和负值，则结果值是实现定义的。