计算机中整数的二进制表示

表示方法

计算机是通过0和1（二进制）来构建的，无法直接表示生活中常用的十进制整数。用计算机内的二进制串来表达十进制就产生了不同的表示方式，这节就来介绍下这些方式。

计算方法

在介绍各种表示方式之前，首先介绍下十进制正整数如何计算对应的二进制表示。算法如下：

while (n > 0) {
    n % 2;
    n = n / 2;
}

其中第二行通过取模操作会依次从低位到高位得到每一位是0还是1，将每次循环得到的结果拼在一起就得到了转换成二进制后的表示。比如\((11)_{10}\)经过转换后就得到了\((1011)_{2}\)。

这种算法仅针对正整数，那么负整数要如何表示呢？一般的规则如下：

最高位当作符号位，一般0代表正数，1代表负数
符号位后的内容一般有三种编码方式：原码、反码和补码

原码

原码表示的负整数就是在正整数的基础上将符号位变成1，比如\((11)_{10}\)的8位二进制表示是\((00001011)_{2}\)，\((-11)_{10}\)的8位二进制表示就是\((10001011)_{2}\)。这种表示是最符合直觉的方式，但是会产生如下问题：

会产生两个0的表示即\((+0)_{10}=(00000000)_{2}\) 和 \((-0)_{10}=(10000000)_{2}\)
一个数和它的相反数相加不等于0：\((1)_{10}+(-1)_{10}=(0)_{10}\) 但 \((00000001)_{2}+(10000001)_{2}=(10000010)_{2}=(-2)_{10}\)

反码

反码表示的负整数就是对应的正整数按位取反，比如\((-11)_{10}=(11110100)_{2}\)。这样就解决了相反数相加的问题：\((-1)_{10}+(1)_{10}=(0)_{10}\) 并且 \((11111110)_{2}+(00000001)_{2}=(00000000)_{2}=(0)_{10}\)（其中最高位的1溢出了）。但还是会有如下问题：

仍然存在两个0的表示 \((+0)_{10}=(00000000)_{2}\) 和 \((-0)_{10}=(11111111)_{2}\)
涉及负数的计算仍然存在错误如：\((-1)_{10}+(-1)_{10}=(-2)_{10}\) 但 \((11111110)_{2}+(11111110)_{2}=(11111100)_{2}=(-3)_{10}\)

补码

补码表示的负整数是在反码的基础上再加1，也就是原码的按位取反再加1。比如\((-11)_{10}\)的反码形式是\((11110101)_{2}\)。这种形式解决了上面两种编码导致的问题，因此计算机中的整数都是用补码的方式来表示的。

只有一个0：\((00000000)_{2}\overset{\text{按位取反}}{\Rightarrow}(11111111)_{2}\overset{\text{+1}}{\Rightarrow}(00000000)_{2}\)
正确的负数运算：\((-1)_{10}+(1)_{10}=(11111111)_{2}+(00000001)_{2}=(00000000)_{2}=(0)_{10}\)，\((-1)_{2}+(-1)_{2}=(11111111)_{2}+(11111111)_{2}=(11111110)_{2}=(-2)_{10}\)。

计算机在大部分情况下都将底层的二进制表现给隐藏了起来，让我们在编程和使用时感觉好像直接操控的整数就是数学中的整数概念。但偶尔也会露出破绽，比较常见的是溢出的情况。一个8位有符号整数能够表示的最大值是\((127)_{10}=(01111111)_{2}\)，这个值再加1的话就会变成\((10000000)_{2}=(-128)_{10}\)。这个情况可以用如下代码来复现：

char ch = 127;
ch += 1;
printf("%hhd\n",ch); // 打印出的是 -128

编程计算十进制整数的二进制表示

本节代码和理论基于C++语言。

bitset

bitset是C++提供的定长容器，支持将整数和字符串格式的二进制互相转换，比如11和"1011"。具体的使用方法可以参考cppreference¹。不过需要注意的一点是bitset只是一个关心每一个bit是0还是1的容器，它不会关心符号位，转换后的整数也永远是无符号的。也就是说负整数经过转换后会变成正数，样例如下：

char ch = -128;
bitset<8> bs(ch);
cout << bs.to_string() << endl << bs.to_ulong() << endl;

上面的代码会输出10000000（-128的补码）和128。

位运算

在了解了整数在计算机中的二进制表示方式，结合前面的计算方法，可以整合成位运算的版本。即每次循环得到最低位的值，然后每次右移一位，这样得到了从低位到高位的表示了：

char ch = 11;
for (int i = 0; i < 8; ++i) {
    cout << (ch & 1);    // 结果会输出11010000，因为是从低位到高位的倒序
    ch >>= 1;
}

最后聊一下右移操作，C++中的右移操作是算数右移，就是在右移的时候最左边会补的是符号位，正数的话补的是0，负数的话补的是1。也就是说负数的话经过不断的右移，最后都会变成\((-1)_{10}=(11111111)_{2}\)（以8位有符号整数为例）。因此如果涉及到有符号整数的右移，建议条件中明确循环次数，比如上面代码的条件如果是while (ch)，那么这个循环就是个死循环。

另外右移一位可以等价于除2也是仅限于正整数如(11 >> 1) == (11 / 2) == 5。对于负数来说也是不成立的。比如(-11 >> 1) != (-11 / 2) == -5。原理是\((-11)_{10}=(11110101)_{2}\overset{右移1位}{\Rightarrow}(11111010)_{2}=(-6)_{10}\)。