在C语言中的大于函数

Question

我知道这是一个老问题，你可能也遇到过，但我的解决方案有一个bug，我不知道该怎么解决。我需要编写一个比较两个整数的函数。我只允许使用以下操作符号（！、~、&、^、|、+、>>、<<），并且不能使用控制结构（if、else循环等）。

isGreater(int x, int y) {
    //returns 1 if x > y.
      return ((y+(~x+1))>>31)&1;
}

我的想法很简单，我们计算y-x，将结果右移31位以得到符号位。如果它是负数，则返回0，否则返回1。然而，当x是负数时，这种方法会失败，并错误地返回1而不是0。我陷入了困境，不知道如何继续。

我们假设整数为32位，使用二进制补码表示。本问题不涉及可移植性。非常感谢任何帮助。

提前致谢。

- Highness

---

假设您知道 int 的大小会导致不可移植的代码。 - John Coleman

@JohnColeman 尝试使用位运算来实现 x > y。我认为可以安全地假设可移植性不是一个问题。 - bolov

@MarkWeston，这仍然存在问题，即右移是实现定义的，有些系统甚至可能不定义int32_t。实际上，这个问题必须伴随着一堆特定于实现的条件。 - M.M

伙计们，这个练习不需要考虑可移植性。这段代码永远不会用于生产环境，只是一个用于位运算的练习。我同意资源可以花在学习其他有用的技能上，而不是这些无用的技巧，但这就是这个练习和问题OP发布的内容。我甚至同意应该教授可移植性，但让我们专注于手头的问题。 - bolov

如果x和y是相反符号的足够大的值，我认为算法会遇到溢出问题。例如，如果x = INT_MIN/2-10和y = INT_MAX/2+20，那么减法的结果很可能是一个正数（假设在溢出时进行了包装，这并不保证），这将无法得出正确的结果。在达到正限制时也存在类似的问题。 - Jonathan Leffler

Answer 1

黑客的乐趣

《黑客的乐趣》一书中有一个章节是比较谓词，这正是我们所需要的。

其中写到：

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;

- harold

Answer 2

首先让我们澄清一下，我们假设：

• 负整数以2的补码表示
• int精确地为32位宽，long long精确地为64位宽
• 对负数进行右移是算术移位

你的解决方案中(~x+1)部分存在问题，它应该返回-x。问题在于INT_MIN的绝对值大于INT_MAX的绝对值，因此当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的结果是E1右移E2位。如果E1具有无符号类型或者E1具有带非负值的有符号类型，则结果的值是E1 / 2E2商的整数部分。如果E1具有带负值的有符号类型，则结果的值是实现定义的。

- MarkWeston