在 C 中使用无符号整数模拟有符号整数

Question

在 Jens Gustedt 的《Modern C》一书中，第 59 页，他解释了如何使用无符号整数来模拟有符号整数。他的示例代码展示了如何实现将两个无符号整数重新解释为有符号整数的比较：

bool is_negative(unsigned a) { 
   unsigned const int_max = UINT_MAX /2;
   return a > int_max;
}

bool is_signed_less(unsigned a, unsigned b) {
   if (is_negative(b) && !is_negative(a)) return false;
   else return a < b; 
} 

我是否误解了这里的某些内容，或者他是否错过了第二个特殊情况 whereis_negative(a) = true和is_negative(b) = false？

例如，如果我们想要a = -1和b = 1，那么，使用补码，我们可以将它们表示为

unsigned int a = UINT_MAX; 
unsigned int b = 1;    

（例如，对于 4 位整数，我们将有 a = 1111 和 b = 0001）。现在我们有is_negative(a)回报true，还有is_negative(b)回报false。当调用时，is_signed_less(a, b)我们最终会进入else子句并且a < b（现在解释为无符号整数）将返回 false。然而，-1 < 1 显然是正确的，因此该函数返回错误的结果。

这是书上代码中的拼写错误还是有什么我不明白的地方？

Answer 1

当人们试图变得“聪明”而不是遵循“保持简单、愚蠢”的最佳实践时，就会发生这种情况。良好的工程涉及尽可能简单地编写代码，例如：

bool is_signed_less_correct (unsigned a, unsigned b) {
  bool is_neg_a = is_negative(a);
  bool is_neg_b = is_negative(b);

  if(is_neg_a != is_neg_b) // one is negative
  {
    return is_neg_a; // if one is negative and it is a, return true otherwise false
  } 

  // both are negative or both are positive
  return a < b;
}

即使这段代码仍然有点太“聪明”，因为它隐式地使用了这样一个事实：-1 == 0xFFFF...是最大的2的补码有符号数，因此a < b无论它们是否为负，只要它们两者具有相同的符号。

当然，您总是会编写一些单元测试来对其进行健全性检查：https://godbolt.org/z/h4nKsffqr

输出：

-2 < -1 ? true  (is_signed_less_gustedt)
-1 < -1 ? false (is_signed_less_gustedt)
-1 <  0 ? false (is_signed_less_gustedt)
 0 < -1 ? false (is_signed_less_gustedt)
 0 <  1 ? true  (is_signed_less_gustedt)
 1 <  0 ? false (is_signed_less_gustedt)
 1 <  1 ? false (is_signed_less_gustedt)

-2 < -1 ? true  (is_signed_less_correct)
-1 < -1 ? false (is_signed_less_correct)
-1 <  0 ? true  (is_signed_less_correct)
 0 < -1 ? false (is_signed_less_correct)
 0 <  1 ? true  (is_signed_less_correct)
 1 <  0 ? false (is_signed_less_correct)
 1 <  1 ? false (is_signed_less_correct)

Answer 2

正如Eric Postpischil在上面的评论中所建议的，这肯定比书本版本（或迄今为止发布的任何其他答案，AFAICT）更简单、更有效：

\n

bool is_signed_less(unsigned a, unsigned b) {\n   unsigned const int_min = UINT_MAX / 2 + 1; /* 0x80000000 on 32-bit platforms */\n   return (a - int_min) < (b - int_min); \n}\n

\n

此代码只是从两个输入中减去偏移量，以便将表示最低可能有符号整数值 ( int_min) 的数字映射到最低可能无符号整数 ( 0)，然后进行无符号比较。

\n

具体来说，减法将最大负有符号整数 ( int_min) 映射到 0，第二大负有符号整数 ( int_min + 1) 映射到 1，第三大负有符号整数 ( int_min + 2) 映射到 2，依此类推。同时，非负有符号整数（其位模式对应于小于 的无符号整数int_min）将导致减法回绕，产生的值高于与任何负输入对应的值。

\n\n

请注意，此代码有几种可能的（和等效的）变体。例如，固定宽度二进制算术如何工作的一个奇怪的数字怪癖意味着它是唯一的无符号整数，int_min其中、 和都相等（对于任何） \xe2\x80\x94 所有这些操作只是翻转 的最高有效位。因此，在上面的代码中，运算符可以替换为或不以任何方式改变代码的行为！x + int_minx - int_minx ^ int_minxx-+^

\n

（理论上，如果其中一些操作恰好在您的 CPU 上运行得更快或管道更好，并且您的编译器不够智能，无法将它们全部优化为相同的汇编代码，那么理论上可能会存在很小的性能差异。如果您'如果您担心可能是这种情况，请对它们进行基准测试并找出答案。不过，它们很可能都同样快。另外，如果您确实想混淆代码并使读者感到困惑，请尝试将运算符混合并匹配成某种东西就像return (a ^ int_min) < (int_min + b)。:P)

\n

Answer 3

是的，这是一个错误。解决这个问题的一种方法是这样的：

bool is_signed_less(unsigned a, unsigned b) {
    bool negativeA = is_negative(a);
    bool negativeB = is_negative(b);
    return (
        (
            negativeA != negativeB ?
            negativeA :
            a < b
        )
    );
}

首先，我分别计算negativeA和negativeB，以避免一次又一次地计算它们。然后，我检查了他们的标志是否不同。

因为如果a和b的符号不同且a为负数，则a < b。

否则，如果a和b的符号不同且a为正，则a > b。

在另一种情况下，当它们的符号相同时，我们只需比较它们。