欢迎访问我的博客：blog.chungzh.cn

基本概念

比特（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$
  $011111\cdots 111111$	$2147483647$
  $100000\cdots 000000$	$2147483648$	$-2147483648$
  $111111\cdots 111111$	$4294967295$	$-1$

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

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

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;
}

输出：

01111111111111111111111111111111 2147483647
10000000000000000000000000000000 -2147483648
00000000000000000000000000000000 0

(t+1)*2 的结果本应是 $1\underbrace{00000\cdots 000000}_{32 个 0}$，依据最高位不进位原则，结果变成了 $\underbrace{00000\cdots 000000}_{32 个 0} = 0$。

补码也被称为“二补数”（Two's complement）。反码也叫“一补数”（Ones' complement），直接把 $C$（正数）的每一位取反表示负 $C$。补码与反码在负数表示中，绝对值相差 $1$。例如在上面的表格中，第一、四行是一对反码，第二、三行是一对反码。作为整数编码，补码比反码有很多优势。除了上面提到的“自然溢出取模”之外，补码重点解决了 $0$ 的编码唯一性问题，能比反码多表示一个数。同时减少特殊判断，在电路设计中简单高效。

形式	加数		和
32 位补码	$111\cdots 111$	$000\cdots 001$	$(1)_{溢出}000\cdots 000$
int	$-1$	$1$	$0$
unsigned int	$4294967295$		$0(\mod 2^{32})$

“反码加一”只是补码所具有的一个性质，不能被定义成补码。负数的补码，是能够和其相反数相加通过溢出从而使计算机内计算结果变为 $0$ 的二进制码。这是补码设计的初衷，具体目标就是让 $1+(-1)= 0$，这利用原码是无法得到的。

所以对于一个 $n$ 位的负数 $-X$，有如下关系：

$$X_补 + (-X)_补 = 1\underbrace{00\cdots 0}_n = 2^n$$

所以 $-X$ 的补码应该是 $2^n-X$ 的二进制编码。

形式	加数		和
32 位补码	$011\cdots 111$	$000\cdots 001$	$100\cdots 000$
int	$2147483647$	$1$	$-2147483648$
unsigned int			$2147483648$

---

因为用二进制表示一个 int 需要写出 32 位，比较繁琐。而用十进制表示，又不容易明显地体现出补码的每一位，所以在程序设计中，常用十六进制来表示一个常数，这样只需要书写 8 个字符，每个字符（$0\sim 9, A\sim F$）代表补码下的 4 个二进制位。C++ 的十六进制常数以 0x 开头，0x 本身只是声明了进制，0x 后面的部分对应具体的十六进制数值。例如：

32 位补码	int（十进制）	int（十六进制）
$000000\cdots 000000$	$0$	$0x0$
$011111\cdots 111111$	$2147483647$	$0x7F\thinspace FF\thinspace FF\thinspace FF$
$00111111 重复4次$	$1061109567$	$0x3F\thinspace 3F\thinspace 3F\thinspace 3F$
$111111\cdots 111111$	$-1$	$0xFF\thinspace FF\thinspace FF\thinspace FF$

上表中的 $0x3F\thinspace 3F\thinspace 3F\thinspace 3F$ 是一个很有用的数值，它有两个特性：

1. 它的两倍不超过 $0x7F\thinspace FF\thinspace FF\thinspace FF$，即 int 能表示的最大正整数。
2. 整数的每 8 位（每个字节）都是相同的。

我们常用的 memset(a, val, sizeof(a)) 初始化一个 int 数组 $a$ 时，把 $val(0x00\sim 0xFF)$ 填充到数组 $a$ 的每个字节上，而一个 int 占用 4 个字节，所以用 memset 只能赋值出每 8 位都相同的 int。

所以，当我们想把一个数组中的数值初始化为正无穷时，为了避免加法上溢或者繁琐的判断，可以用 memset(a, 0x3f, sizeof(a)) 给数组赋 $0x3F\thinspace 3F\thinspace 3F\thinspace 3F$ 的值。

移位运算

左移

在二进制表示下把数字同时向左移动，低位以 $0$ 填充，高位越界后舍弃。

算术右移

在二进制补码表示下把数字同时向右移动，高位以符号位填充，低位越界后舍弃。

$$n>>1 = \lfloor \frac{n}{2.0} \rfloor$$

注意，整数除法在 C++ 中的实现是向零取整（舍弃小数部分），例如 $(-3)/2=-1$，$3/2=1$。

逻辑右移

在二进制补码表示下把数字同时向右移动，高位以 $0$ 填充，低位越界后舍弃。

无符号整数右移使用的是逻辑右移。对于有符号整数，在 C++ 20 前并没有规定使用算术右移还是逻辑右移（大多数平台上进行算术右移）。C++ 20 开始才规定使用算术右移。

参考资料

• 《算法竞赛进阶指南》
• 补码的计算方法 - Murphy - 知乎
• cppreference.com