基本概念

比特（bit，亦称二进制位）是指 1 位二进制的数码（0 或 1），是计算机中信息的最小单位。

字节（byte）：一个字节由 8 位组成。

熟练地运用位运算，可以提高我们程序的时空效率。

计算机中的整数存储与运算

下面以 32 位二进制数，即 C++ 中的 int 和 unsigned int 类型为例。

原码、反码

简单介绍一下：

1. 原码：最高位为符号位，正数为 $0$，负数为 $1$，其余所有位为十进制数的绝对值。

   • 优点：对人类而言最直观。
   • 缺点：无法将减法转换成加法运算。如：$1-1=1+(-1)=0001+1001=1010=-2$；$0$ 有两种表示方法 $0000$ 和 $1000$。

2. 反码：最高位为符号位，正数为 $0$，负数为 $1$。正数的反码等于本身，负数的反码除符号位外，各位取反。

   • 优点：解决了减法运算的问题。$1-1=1+(-1)=0001+1110=1111=0$
   • 缺点：$0$ 有两种表示方法 $0000$ 和 $1111$；减法算法规则较复杂，需要额外判断溢出。

补码

• 32 位无符号整数 unsigned int： 直接把这 32 位编码 $C$ 看作 32 位二进制数 $N$。

• 32 位有符号整数 int： 以最高位作为符号位，$0$ 表示非负数，$1$ 表示负数。

  对于最高位为 $0$ 的每种编码 $C$，直接看做 32 位二进制数 $S$。

  同时，定义该编码按位取反后得到的编码 ~C 表示的数值为 $-1-S$。

  32 位补码表示	unsigned int	int
  $000000\cdots 000000$	$0$	$0$
  $011111\cdots 111111$	$2147483647$	$2147483647$
  $100000\cdots 000000$	$2147483648$	$-2147483648$
  $111111\cdots 111111$	$4294967295$	$-1$

可以发现，在补码下，每个数值都有唯一的表示方式，并且任意两个数值做加减法运算，都等价于在 32 位补码下做最高位不进位的二进制加减法运算。发生上/下溢出时，32 位无符号整数和有符号整数都相当于自动对 $2^{32}$ 取模（回绕）。

这也解释了有符号整数算术上溢时会出现负数的现象。我们来对 int 的溢出做一个实验：

1
2
3
4
5
6
7
8

void print(int t) { cout << bitset<32>(t) << " " << t << endl; }
int main() {
  int t = 2147483647;
  print(t);
  print(t + 1);
  print((t + 1) * 2);
  return 0;
}

输出：

1
2
3

01111111111111111111111111111111 2147483647
10000000000000000000000000000000 -2147483648
00000000000000000000000000000000 0

(t+1)*2 的结果本应是 $1\underbrace{00000\cdots 000000}...