0x01 位运算

bit 是度量信息的单位，包含 0 和 1 两种状态。计算机的各种运算最后无不归结为一个个 bit 的变化。熟练掌握并利用位运算，能够帮助我们理解程序运行中的种种表现，提高程序运行的时空效率，降低编程复杂度。

读者可能已经发现，本书的章节目录是以 $0 \times 00 \sim 0 \times \mathrm{FF}$ 这些由数字 $0 \sim 9$ 与字母A~F表示的2位十六进制整数进行编号的，其中“0x”表示十六进制。正文即本章由 $0 \times 00$ 开始，前言分配序号0xFF，后记分配序号 $0 \times 7\mathrm{F}$ 。这就是以最高二进制位为正负符号位的“补码”形式表示的8位二进制数。在C++中，8位二进制数对应char类型，范围为-128～127，其中0xFF代表-1，0x7F代表最大值127。

在阅读本节之前，读者应该对以下算术位运算有一个初步的认识①：

它们不局限于逻辑运算，均可作用于二进制整数。为了避免混淆，本书统一用单词xor表示异或运算，而用符号“^”表示乘方运算（虽然该符号在 $\mathrm{C}++$ 中表示异或）。

另外，在 $m$ 位二进制数中，为方便起见，通常称最低位为第0位，从右到左依此类推，最高位为第 $m - 1$ 位。本书默认使用这种表示方法来指明二进制数以及整数在二进制表示下的位数。

下面我们以32位二进制数，即 $C++$ 的int与unsignedint类型为例详细介绍计算机中的整数存储与运算。

补码

32 位无符号整数 unsigned int:

直接把这32位编码 $C$ 看作32位二进制数 $N$ 。

32 位有符号整数 int:

以最高位为符号位，0表示非负数，1表示负数。

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

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

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

补码也被称为“二补数”。还有一种编码称为反码，也叫“一补数”，直接把 $C$ 的每一位取反表示负 $C$ 。补码与反码在负数表示中，绝对值相差 1。例如，在上表中，第 1、4 行是一对反码，第 2、3 行是一对反码。作为整数编码、存储和运算的方式，补码与反码相比有许多优势。除了上面提到的“自然溢出取模”之外，补码重点解决了 0 的编码唯一性问题，能比反码多表示一个数，同时减少特殊判断，在电路设计中极其简单、高效。

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

上表中的0x3F 3F 3F 3F 是一个很有用的数值，它是满足以下两个条件的最大整数。

1. 整数的两倍不超过 $0 \times 7 \mathrm{~F} \times \mathrm{F} \times \mathrm{F} \times \mathrm{F}$ ，即 int 能表示的最大正整数。

2. 整数的每8位（每个字节）都是相同的。

我们在程序设计中经常需要使用memset(a, val, sizeof(a))初始化一个int数组a，该语句把数值val（0x00~0xFF）填充到数组a的每个字节上，而1个int占用4个字节，所以用memset只能赋值出“每8位都相同”的int。

综上所述，0x7F 7F 7F 7F 是用 memset 语句能初始化出的最大数值。不过，当需要把一个数组中的数值初始化成正无穷时，为了避免加法算术上溢或者繁琐的判断，我们经常用 memset(a, 0x3f, sizeof(a)) 给数组赋 0x3F 3F 3F 3F 的值来代替。该语句在后续章节的参考程序中将会多次出现。

移位运算

左移

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

算术右移

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

算术右移等于除以2向下取整， $(-3)\gg 1 = -2$ ， $3\gg 1 = 1$ 。

值得一提的是，“整数/2”在 $\mathbf{C} + +$ 中实现为“除以2向零取整”， $(-3) / 2 = -1, 3 / 2 = 1$ 。请读者自己尝试使用 $\mathbf{C} + +$ 编译器编译运行类似的语句，检查运算结果。

逻辑右移

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

C++语法没有规定右移的实现方式，使用算术右移还是逻辑右移由编译器决定。一般的编译器（较新版本的GNU C++与Visual Studio C++）均使用算术右移。除非特殊提示，我们默认右移操作采用算术右移方式实现。

【例题】 $a^{\wedge}b$

求 $a$ 的 $b$ 次方对 $p$ 取模的值，其中 $1 \leq a, b, p \leq 10^9$ 。

相关题目：POJ1995 Raising Modulo Numbers

根据数学常识，每一个正整数可以唯一表示为若干指数不重复的2的次幂的和。也就是说，如果 $b$ 在二进制表示下有 $k$ 位，其中第 $i(0 \leq i < k)$ 位的数字是 $c_i$ ，那么：

于是：

因为 $k = [\log_2(b + 1)]$ （其中「]表示上取整），所以上式乘积项的数量不多于 $[\log_2(b + 1)]$ 个。又因为：

所以我们很容易通过 $k$ 次递推求出每个乘积项，当 $c_{i} = 1$ 时，把该乘积项累积到答案中。 $b \& 1$ 运算可以取出 $b$ 在二进制表示下的最低位，而 $b >> 1$ 运算可以舍去最低位，在递推的过程中将二者结合，就可以遍历 $b$ 在二进制表示下的所有数位 $c_{i}$ 。整个算法的时间复杂度为 $O(\log_2 b)$ 。

int power(int a, int b, int p) { // calculate (a ^ b) mod p
    int ans = 1 % p;
    for (; b; b >= 1) {
        if (b & 1) ans = (long long) ans * a % p;

a = (long long)a * a % p;  
}  
return ans;

在上面的代码片段中，我们通过“右移（>>）”“与（&）”运算的结合，遍历了 $b$ 的二进制表示下的每一位。在循环到第 $i$ 次时（从0开始计数），变量 $a$ 中存储的是 $a^{2^i}$ ，若 $b$ 该位为1，则把此时的变量 $b$ 累积到答案 ans 中。

值得提醒的是，在 $C++$ 语言中，两个数值执行算术运算时，以参与运算的最高数值类型为基准，与保存结果的变量类型无关。换言之，虽然两个32位整数的乘积可能超过int类型的表示范围，但是CPU只会用1个32位寄存器保存结果，造成我们常说的越界现象。因此，我们必须把其中一个数强制转换成64位整数类型long long参与运算，从而得到正确的结果。最终对 $p$ 取模以后，执行赋值操作时，该结果会被隐式转换成int存回ans中。

于是一个问题就出现了。因为 $C++$ 内置的最高整数类型是 64 位，若运算 $a * b \mod p$ 中的三个变量 $a, b, p$ 都在 $10^{18}$ 级别，则不存在一个可供强制转换的 128 位整数类型，我们需要一些特殊的处理办法。

【例题】64位整数乘法

求 $a$ 乘 $b$ 对 $p$ 取模的值，其中 $1 \leq a, b, p \leq 10^{18}$ 。

方法一

类似于快速幂的思想，我们把整数 $b$ 用二进制表示，即 $b = c_{k}2^{k - 1} + c_{k - 1}2^{k - 2} + \dots +c_{0}2^{0}$ ，那么 $a*b = c_k*a*2^{k - 1} + c_{k - 1}*a*2^{k - 2} + \dots +c_0*a*2^0$ 。

因为 $a * 2^i = (a * 2^{i-1}) * 2$ ，若已求出 $a * 2^{i-1} \bmod p$ ，则计算 $(a * 2^{i-1}) * 2 \bmod p$ 时，运算过程中每一步的结果都不超过 $2 * 10^{18}$ ，仍然在64位整数long long的表示范围内，所以很容易通过 $k$ 次递推求出每个乘积项。当 $c_i = 1$ 时，把该乘积项累加到答案中即可。时间复杂度为 $O(\log_2 b)$ 。

long long mul(long long a, long long b, long long p) {  
    long long ans = 0;  
    for ( ; b ; b >= 1 ) {  
        if (b & 1) ans = (ans + a) % p;  
            a = a * 2 % p;  
    }  
    return ans;

方法二

利用 $a * b \mod p = a * b - \lfloor a * b / p \rfloor * p$ ，其中 $\lfloor \rfloor$ 表示下取整。

首先，当 $a, b < p$ 时， $a * b / p$ 下取整以后一定也小于 $p$ 。我们可以用浮点数执行 $a * b / p$ 的运算，而不用关心小数点之后的部分。浮点类型 long double 在十进制下的有效数字有 $18 \sim 19$ 位，足够胜任。当浮点数的精度不足以保存精确数值时，它会像科学计数法一样舍弃低位，正好符合我们的要求。

另外，虽然 $a * b$ 和 $[a * b / p] * p$ 可能很大，但是二者的差一定在 $0 \sim p - 1$ 之间，我们只关心它们较低的若干位即可。所以，我们可以用 long long 来保存 $a * b$ 和 $[a * b / p] * p$ 各自的结果。整数运算溢出相当于舍弃高位，也正好符合我们的要求。

long long mul(long long a, long long b, long long p) {  
    a % = p, b % = p; // 当 a, b 一定在 0~p 之间时，此行不必要  
    long long c = (long double) a * b / p;  
    long long ans = a * b - c * p;  
    if (ans < 0) ans += p;  
    else if (ans >= p) ans -= p;  
    return ans;  
}

$\spadesuit$ 二进制状态压缩

二进制状态压缩，是指将一个长度为 $m$ 的 bool 数组用一个 $m$ 位二进制整数表示并存储的方法。利用下列位运算操作可以实现原 bool 数组中对应下标元素的存取。

这种方法运算简便，并且节省了程序运行的时间和空间。当 $m$ 不太大时，可以直接使用一个整数类型存储。当 $m$ 较大时，可以使用若干个整数类型（int数组），也可以直接利用 C++ STL 为我们提供的 bitset 实现（第 0x71 节）。

【例题】最短Hamilton路径

给定一张 $n(n \leq 20)$ 个点的带权无向图，点从 $0 \sim n - 1$ 标号，求起点 0 到终点

$n - 1$ 的最短Hamilton路径。

Hamilton路径的定义是从0到 $n - 1$ 不重不漏地经过每个点恰好一次。

*扩展题目：POJ2288 Islands and Bridges

很容易想到本题的一种“朴素”①做法，就是枚举 $n$ 个点的全排列，计算路径长度取最小值，时间复杂度为 $O(n*n!)$ ，使用下面的二进制状态压缩 DP 可以优化到 $O(n^{2}*2^{n})$ 。关于状态压缩动态规划将在第 0x56 节详细讲解。

在任意时刻如何表示哪些点已经被经过，哪些点没有被经过？可以使用一个 $n$ 位二进制数，若其第 $i$ 位 $(0 \leq i < n)$ 为1，则表示第 $i$ 个点已经被经过，反之未被经过。在任意时刻还需要知道当前所处的位置，因此我们可以使用 $F[i, j] (0 \leq i < 2^n, 0 \leq j < n)$ 表示“点被经过的状态”对应的二进制数为 $i$ ，且目前处于点 $j$ 时的最短路径。

在起点时，有 $F[1,0] = 0$ ，即只经过了点 0（ $i$ 只有第 0 位为 1），目前处于起点 0，最短路长度为 0。方便起见，我们将 $F$ 数组其他的值设为无穷大。最终目标是 $F[(1 \ll n) - 1, n - 1]$ ，即经过所有点（ $i$ 的所有位都是 1），处于终点 $n - 1$ 的最短路。

在任意时刻，有公式 $F[i,j] = \min \{F[i\text{xor} (1\ll j),k] + \text{weight}(k,j)\}$ ，其中 $0\leq k < n$ 并且 $((i\gg j)\& 1) = 1$ ，即当前时刻“被经过的点的状态”对应的二进制数为 $i$ ，处于点 $j$ 。因为 $j$ 只能被恰好经过一次，所以一定是刚刚经过的，故在上一时刻“被经过的点的状态”对应的二进制数的第 $j$ 位应该赋值为0，也就是 $i\text{xor} (1\ll j)$ 。另外，上一时刻所处的位置可能是 $i\text{xor} (1\ll j)$ 中任意一个是1的数位 $k$ ，从 $k$ 走到 $j$ 需经过 $\text{weight}(k,j)$ 的路程，可以考虑所有这样的 $k$ 取最小值。这就是该公式的由来。

int f[1 << 20][20];  
int hamilton(int n, int weight[20][20]) {  
    memset(f, 0x3f, sizeof(f));  
    f[1][0] = 0;  
    for (int i = 1; i < 1 << n; i++)  
        for (int j = 0; j < n; j++) if (i >> j & 1)  
            for (int k = 0; k < n; k++) if (i >> k & 1)  
                f[i][j] = min(f[i][j], f[i^1 << j][k] + weight[k][j]);  
    return f[(1 << n) - 1][n - 1];  
}

提醒：一些运算符优先级从高到低的顺序如下表所示。最需要注意的地方是：大小关系比较的符号优先于“位与”“异或”“位或”运算。在程序实现时，如果不确定优先级，建议加括号保证运算顺序的正确性。

成对变换

通过计算可以发现，对于非负整数 $n$

当 $n$ 为偶数时， $n \times \operatorname{or} 1$ 等于 $n + 1$ 。

当 $n$ 为奇数时， $n \text{ XOR } 1$ 等于 $n - 1$ 。

因此，“0与1”“2与3”“4与5”……关于xor1运算构成“成对变换”。

这一性质经常用于图论邻接表中边集的存储。在具有无向边（双向边）的图中把一对正反方向的边分别存储在邻接表数组的第 $n$ 与 $n + 1$ 位置（其中 $n$ 为偶数），就可以通过 $\mathrm{xor}1$ 的运算获得与当前边 $(x,y)$ 反向的边 $(y,x)$ 的存储位置。详细应用我们将在讲解邻接表（第0x13节）时给出。

$\spadesuit$ lowbit运算

lowbit(n) 取出非负整数 $n$ 在二进制表示下最低位的 1 以及它后边的 0 构成的数值。

设 $n > 0$ ， $n$ 的第 $k$ 位是1，第 $0\sim k - 1$ 位都是0。

为了实现 lowbit 运算，先把 $n$ 取反，此时第 $k$ 位变为 0，第 $0 \sim k - 1$ 位都是 1。再令 $n = n + 1$ ，此时因为进位，第 $k$ 位变为 1，第 $0 \sim k - 1$ 位都是 0。

在上面的取反加1操作后， $n$ 的第 $k + 1$ 到最高位恰好与原来相反，所以 $n\& (\sim n + 1)$ 仅有第 $k$ 位为1，其余位都是0。而在补码表示下， $\sim n = -1 - n$ ，因此：

lowbit运算配合Hash（第0x14节）可以找出整数二进制表示下所有是1的位，所花费的时间与1的个数同级。另外，lowbit运算也是树状数组（第0x42节）中的一个基本运算。

while (cin >> n) { // 对多次询问进行求解

while  $(n > 0)$  {cout  $<  <   H[n\& -n] <   <   ^{\prime}{}_{!}$  n  $\equiv$  n & -n;1

GCC编译器提供了一些内置函数①，可以高效计算lowbit以及二进制数中1的个数。不过，这些函数并非C语言标准，有的函数更是与机器相关的。另外，部分算法竞赛禁止使用下划线开头的库函数，故这些内置函数尽量不要随便使用。

int __builtin_ctz(unsigned int x)  
int __builtin_ctzl(unsigned long long x)

返回 $x$ 的二进制表示下最低位的 1 后边有多少个 0。

int __builtin_popcount(unsigned int x)  
int __builtin_popcount11(unsigned long long x)

返回 $x$ 的二进制表示下有多少位为 1。