位运算的概念

整数在计算机中的表示

二进制表示

程序中的所有数在计算机中的表示形式都是二进制，二进制使用两个数码：$0$ 和 $1$。

一位二进制数称为一个比特（bit），可能取值有 $2$ 个，$k$ 位二进制数的可能取值有 $2^k$ 个。

$8$ 个比特组成一个字节（byte），一个字节的可能取值有 $2^8=256$ 个。

计算机中有多种表示整数的数据类型，每种数据类型的字节数各不相同，取值范围也各不相同。Java 的整数数据类型有以下四种。

• 字节型，用 $\text{byte}$ 表示，包含 $1$ 个字节，即 $8$ 位二进制数，可能取值有 $2^8$ 个。

• 短整型，用 $\text{short}$ 表示，包含 $2$ 个字节，即 $16$ 位二进制数，可能取值有 $2^{16}$ 个。

• 整型，用 $\text{int}$ 表示，包含 $4$ 个字节，即 $32$ 位二进制数，可能取值有 $2^{32}$ 个。

• 长整型，用 $\text{long}$ 表示，包含 $8$ 个字节，即 $64$ 位二进制数，可能取值有 $2^{64}$ 个。

有符号类型和无符号类型

计算机中的数据类型包括有符号类型和无符号类型，这两种类型表示的整数分别称为有符号整数和无符号整数。

有符号整数中，最高位用于表示符号，因此最高位又称符号位，最高位是 $0$ 表示非负数，最高位是 $1$ 表示负数。无符号整数中，不存在用于表示符号的位，因此无符号整数都是非负数。

有符号整数的表示范围包括非负整数和负整数，无符号整数的表示范围只有非负整数。在位数相同的情况下，无符号整数可以表示的最大值大于有符号整数可以表示的最大值。

C、C++、C# 等语言支持有符号类型和无符号类型，Java 只支持有符号类型。

机器数和真值

一个数在计算机中的二进制表示形式称为这个数的机器数。机器数是有符号数，最高位是符号位，$0$ 表示非负数，$1$ 表示负数。

因为机器数的最高位是符号位，所以机器数的形式值不一定等于真正数值。为了区别形式值和真正数值，将机器数对应的真正数值称为真值。

考虑 $1$ 个字节的二进制数表示的机器数。十进制的 $+20$ 对应的机器数是 $00010100$，十进制的 $-20$ 对应的机器数是 $10010100$。

机器数 $00010100$ 的形式值是 $20$，与真正数值相等。机器数 $10010100$ 的形式值是 $148$，与真正数值不相等。

原码、反码和补码

原码、反码和补码的表示方法

原码是机器数的符号位加上机器数的真值的绝对值，最高位是符号位，其余位表示数值。

反码和补码在原码的基础上得到。

非负数的反码与原码相同，负数的反码是将原码的除了符号位之外的每一位取反。

非负数的补码与原码相同，负数的补码是将原码的除了符号位之外的每一位取反，然后加 $1$。

考虑 $1$ 个字节的二进制数表示。

$+20$ 的原码、反码和补码都是 $00010100$。

$-20$ 的原码是 $10010100$，反码是 $11101011$，补码是 $11101100$。

根据上述例子可知，同一个非负数的原码、反码和补码的表示方法相同，同一个负数的原码、反码和补码的表示方法不同。其中，原码是人脑最容易理解和计算的表示方法，相比之下，反码和补码的表示方法不直观，通常需要转换成原码才能计算其数值。

计算机中的表示

虽然有符号数的二进制表示有原码、反码和补码三种表示方法，但是计算机使用补码的表示方法。

对于计算机而言，判断符号位将导致运算变得复杂，为了简化运算，将符号位也参与运算。

对于 $k$ 位二进制数表示，可能取值有 $2^k$ 个。考虑原码、反码和补码三种表示方法可以表示的数值范围。

使用原码，可以表示的数值范围是 $[-(2^{k-1}-1),2^{k-1}-1]$，该范围的不同数值有 $2^k-1$ 个，数值 $0$ 存在 $+0$ 和 $-0$ 的两个不同的原码表示。使用原码的另一个问题是，做减法运算会导致错误的结果。虽然原码是人脑容易理解和计算的表示方法，但是由于原码存在上述两个问题，因此不适用于计算机。

使用反码，可以表示的数值范围是 $[-(2^{k-1}-1),2^{k-1}-1]$，该范围的不同数值有 $2^k-1$ 个，数值 $0$ 存在 $+0$ 和 $-0$ 的两个不同的反码表示。虽然使用反码可以解决减法运算结果错误的问题，但是仍存在 $+0$ 和 $-0$ 的问题，因此不适用于计算机。

使用补码，可以表示的数值范围是 $[-2^{k-1},2^{k-1}-1]$，该范围的不同数值有 $2^k$ 个，每个数值都只有一个补码表示。补码可以同时解决减法运算结果错误的问题和存在 $+0$ 和 $-0$ 的问题，而且比原码和反码多表示一个最小值，因此计算机使用补码的表示方法。

位运算

在计算机的底层，一切运算都是基于位运算实现的。

位运算共有 $6$ 种，分别是：与、或、异或、取反、左移和右移，其中左移和右移运算统称移位运算，移位运算又分为算术移位和逻辑移位。

上述位运算中，只有取反是一元运算，其余的都是二元运算。

与、或、异或和取反

与运算的符号是 $\&$，运算规则是：对于每个二进制位，当两个数对应的位都是 $1$ 时，结果是 $1$，否则结果是 $0$。

$$\begin{array}{rl}0\&0& =0\\ 0\&1& =0\\ 1\&0& =0\\ 1\&1& =1\end{array}$$

或运算的符号是 $|$，运算规则是：对于每个二进制位，当两个数对应的位中至少有一个是 $1$ 时，结果是 $1$，否则结果是 $0$。

$$\begin{array}{rl}0|0& =0\\ 0|1& =1\\ 1|0& =1\\ 1|1& =1\end{array}$$

异或运算的符号是 $\oplus$（代码中的异或运算符是 $\wedge$），运算规则是：对于每个二进制位，当两个数对应的位中有且只有一个是 $1$ 时，结果是 $1$，否则结果是 $0$。

$$\begin{array}{rl}0\oplus 0& =0\\ 0\oplus 1& =1\\ 1\oplus 0& =1\\ 1\oplus 1& =0\end{array}$$

取反运算的符号是 $\sim$，运算规则是：对一个数的每个二进制位进行取反操作，$0$ 变成 $1$，$1$ 变成 $0$。

$$\begin{array}{rl}\sim 0& =1\\ \sim 1& =0\end{array}$$

移位运算

移位运算按照移位方向分类可以分成左移和右移，按照是否带符号分类可以分成算术移位和逻辑移位。

左移运算时，将全部二进制位向左移动若干位，高位丢弃，低位补 $0$。对于左移运算，算术移位和逻辑移位是相同的。左移运算的符号是 $<<$。

右移运算时，将全部二进制位向右移动若干位，低位丢弃，高位的补位由算术移位或逻辑移位决定。

• 算术右移时，高位补最高位。

• 逻辑右移时，高位补 $0$。

Java 中，算术右移运算的符号是 $>>$，逻辑右移运算的符号是 $>>>$。

C、C++、C# 等语言中，右移运算的符号是 $>>$，不区分算术右移和逻辑右移，而是根据数据类型中的有符号类型和无符号类型区分算术右移和逻辑右移。对于有符号类型，右移运算为算术右移；对于无符号类型，右移运算为逻辑右移。

移位运算与乘除法的关系

移位运算与乘除法有密切的关联性，使用位运算实现乘除法的效率高于直接计算乘除法的效率。

左移运算对应乘法运算。将一个数左移 $k$ 位，等价于将这个数乘以 $2^k$。如果左移运算之后的结果超出特定类型的整数的表示范围，则运算结果溢出，最高位被舍弃。

算术右移对应除法运算。将一个数右移 $k$ 位，相当于将这个数除以 $2^k$，结果向下取整。

将一个数左移 $k$ 位和使用乘号计算这个数乘以 $2^k$ 的结果一定相同，但是将一个数右移 $k$ 位和使用除号计算这个数除以 $2^k$ 的结果不一定相同。由于使用除号计算整数除法的结果向零取整，而使用算术右移计算整数除法的结果向下取整，因此当被除数是非负数时两者的结果相同，当被除数是负数时两者的结果可能不同。

位运算的性质

位运算的性质有很多，此处列举位运算中的与、或、异或和取反的常见性质。假设以下出现的变量都是有符号整数。

• 与运算性质：$0\&x=0$，$x\&0=0$，$x\&(-1)=x$，$x\&(\sim x)=0$。

• 或运算性质：$0|x=x$，$x|0=x$，$x|(\sim x)=-1$。

• 异或运算性质：$0\oplus x=x$，$x\oplus 0=x$，$x\oplus x=0$。

• 取反运算性质：$-1=\sim 0$，$-x=\sim (x-1)$。

• 幂等律（注意异或运算不适用）：$x\&x=x$，$x|x=x$。

• 交换律：$x\&y=y\&x$，$x|y=y|x$，$x\oplus y=y\oplus x$。

• 结合律：$(x\&y)\&z=x\&(y\&z)$，$(x|y)|z=x|(y|z)$，$(x\oplus y)\oplus z=x\oplus (y\oplus z)$。

• 分配律：$(x\&y)|z=(x|z)\&(y|z)$，$(x|y)\&z=(x\&z)|(y\&z)$，$(x\oplus y)\&z=(x\&z)\oplus (y\&z)$。

• 德·摩根律：$\sim (x\&y)=(\sim x)|(\sim y)$，$\sim (x|y)=(\sim x)\&(\sim y)$。

• 其他性质：

  • $x\&(x-1)$ 的结果为将 $x$ 的二进制表示的最后一个 $1$ 变成 $0$。

  • $x\&(-x)$（与 $x\&(\sim (x-1))$ 等价）的结果为只保留 $x$ 的二进制表示的最后一个 $1$，其余的 $1$ 都变成 $0$。

上述性质在位运算的题目中经常使用到。

目录

1. 位运算题目：数组异或操作
2. 位运算题目：解码异或后的数组
3. 位运算题目：交替位二进制数
4. 位运算题目：位 1 的个数
5. 位运算题目：比特位计数
6. 位运算题目：汉明距离
7. 位运算题目：颠倒二进制位
8. 位运算题目：二进制手表
9. 位运算题目：二进制间距
10. 位运算题目：数字的补数
11. 位运算题目：数字转换为十六进制数
12. 位运算题目：两整数之和
13. 位运算题目：或运算的最小翻转次数
14. 位运算题目：最大单词长度乘积
15. 位运算题目：UTF-8 编码验证
16. 位运算题目：汉明距离总和
17. 位运算题目：数字范围按位与
18. 位运算题目：N 天后的牢房
19. 位运算题目：形成两个异或相等数组的三元组数目
20. 位运算题目：连接连续二进制数字
21. 位运算题目：格雷编码
22. 位运算题目：循环码排列
23. 位运算题目：解码异或后的排列
24. 位运算题目：两数相除
25. 位运算题目：寻找重复数
26. 位运算题目：按位与为零的三元组
27. 位运算题目：安排电影院座位
28. 位运算题目：黑板异或游戏
29. 位运算题目：找到最接近目标值的函数值
30. 位运算题目：找出最长的超赞子字符串