确定一个数字是否可以表示为 n 位整数（二进制补码）

Question

关于二进制补码，我有点难以理解如何在 C 中使用位。

这是家庭作业的一部分，但我不是在寻找代码答案，而是要了解二进制补码表示发生了什么。

我的任务是将一个数字限制为特定的位数 (n)，并确定给定的数字是否可以用 n 位数的二进制补码表示。

根据示例，5 不能表示为 3 位整数，而 -4 可以表示为 3 位整数。

为什么是这样？

---

编辑：我详细解释了我的思考过程，但意识到我完全偏离了所以决定省略它。

我最初的推理是看看允许 5 和 -5、4 和 -4 以 3 位表示是否有意义。但这没有意义，因为这并没有真正解决问题。

我理解 5 和 -4 如何表示为二进制补码。例如，作为 4 位：

5：0101

-4：1100

---

第二次编辑：

为了澄清起见，决定添加我原来的推理：

5 是 0101，-5 是 1011。
我可以看到当限制为 3 位时，5 不能用二进制补码表示，因为没有第 4 位，我们就不能表示 -5 是负数。我们需要 1011 中的额外 1。如果我们最多只能有 3 位，我们将有 011，并且无法区分 -5 和 3，后者是 4 位中的 0011，以及 011在 3 位。这个推理正确吗？

4 是 0100，-4 是 1100。
这里我很困惑。我不明白为什么 -4 可以用 3 位表示为二进制补码整数。

4 表示为 0100，100 表示为 3 位。-4 是，如果我们从 4 (100) 开始，我们翻转 100 (011)，然后加上 1 (100)，我们再次剩下 100（3 位）。在 4 位中，我相信这表示为 1100。

我的困惑是，对于 1100，我们是否需要额外的 1 来区分 -4 和 4，即 0100？如果我们只有 3 位，我们如何区分 100 和 100？

Answer 1

为了理解这一点，需要记住，尽管它在现代硬件中无处不在，但补码不是自然法则，而是人类构造。

假设我们想将一个整数打包成 n 位。为简单起见，让 n=3。显然，我们可以选择任意 2 ³ =8 个整数，前提是我们是一致的，但在算术方面，有些选择比其他选择更容易。

无符号整数是直截了当的。有一个自然映射：

Encoding  Value
 000        0
 001        1
 010        2
 011        3
 100        4
 101        5
 110        6
 111        7

这只是值的二进制编码，带有零填充。零的所有位都为零，这很方便。加法和减法只是工作，模 2 ⁿ。

有符号整数更棘手。在普遍采用二进制补码之前，至少还使用了其他两种表示形式：有符号幅度(SM) 和二进制补码(1C)。

Encoding   SM    1C
 000        0     0 
 001        1     1
 010        2     2
 011        3     3
 100       -0    -3
 101       -1    -2
 110       -2    -1
 111       -3    -0

两种编码 SM 和 1C 都使用 n 位来存储从 -(2 ^n-1 -1) 到 2 ^n-1 -1 的有符号整数。两种编码都以与以前相同的方式存储正整数。好：两者在正负方向上的距离相同。好：两者都使负性测试变得容易（除了零，这通常需要特殊处理）。好：两者都使取反变得容易（SM：翻转符号位；1C：翻转所有位）。不好：两者都包含一个不必要的“负零”，这使相等性测试和算术测试复杂化。

这将我们带到了二进制补码 (2C)。

Encoding   2C
 000        0
 001        1
 010        2
 011        3
 100       ???
 101       -3
 110       -2
 111       -1

在这里，我们像以前一样从正整数开始，然后通过从零“向后计数”直到我们在中间相遇来得到负整数。好：这使得算术非常自然，就像在无符号情况下一样简单。不好：否定比在 SM 或 1C 中更棘手。

但是我们如何处理带有 ??? 的行？我们已经拥有 1C 和 SM 中的所有数字。我们可以选择 4 或 -4，或者“未定义”。2C 中的约定是我们选择负值。这为我们提供了 -4 到 +3 的范围，或者更一般的 -2 ^n-1到 2 ^n-1 -1。这个不对称范围很尴尬（我们有 -4 但不是 +4，结果 -4 是它自己的负数！[1]），但保留了所有负数都设置了最高位的属性，并确保每个编码都有一个与之关联的值。

所以（终于！）关于你的问题。为什么 -4 可以用二进制补码表示为 3 位整数？因为这是最不坏的选择。

进一步阅读：维基百科上的签名数字表示。

[1] 这是一个测试程序，用于演示这是多么混乱。这int是 32 位宽。

[~]% cat 2c.c
#include <stdio.h>
#include <limits.h>

int main(void) {
    int i = INT_MAX;
    int j = INT_MIN;

    printf ("   i = % d (hex %x)\n", i, i);
    printf ("   j = % d (hex %x)\n", j, j);
    printf ("  -i = % d (hex %x)\n", -i, -i);
    printf ("  -j = % d (hex %x)\n", -j, -j);
    printf ("i*-1 = % d (hex %x)\n", i*-1, i*-1);
    printf ("j*-1 = % d (hex %x)\n", j*-1, j*-1);
    printf ("i/-1 = % d (hex %x)\n", i/-1, i/-1);
    printf ("j/-1 = % d (hex %x)\n", j/-1, j/-1);

    return 0;
}

请注意，根据 C 标准，否定最负整数 ( INT_MIN) 是未定义的行为，因此使用三种否定方法中的一种来终止程序是完全合理的：

[~]% clang -Wall 2c.c -o 2c && ./2c
   i =  2147483647 (hex 7fffffff)
   j = -2147483648 (hex 80000000)
  -i = -2147483647 (hex 80000001)
  -j = -2147483648 (hex 80000000)
i*-1 = -2147483647 (hex 80000001)
j*-1 = -2147483648 (hex 80000000)
i/-1 = -2147483647 (hex 80000001)
zsh: floating point exception  ./2c

这是安全漏洞的来源（遗憾的是，大多数真实漏洞都没有有趣的演练）。