7.6 位运算

---

1. 位运算简介

1.1 位运算与二进制基础

位运算（Bit Operation）：计算机内部所有数据均以「二进制（Binary）」形式存储。位运算是直接对二进制位进行操作的运算方式，能够极大提升程序的执行效率。

在正式学习位运算之前，先简单了解「二进制数」的基本概念。

二进制数

二进制数（Binary）：仅由 $0$ 和 $1$ 两个数字组成。二进制数中的每一位（$0$ 或 $1$）称为一个「位（Bit）」。

我们日常使用的十进制数包含 $0 \sim 9$ 共 $10$ 个数字，进位规则为「满十进一」。例如：

1. $7_{(10)} + 2_{(10)} = 9_{(10)}$：$7_{(10)}$ 加 $2_{(10)}$ 得 $9_{(10)}$。
2. $9_{(10)} + 2_{(10)} = 11_{(10)}$：$9_{(10)}$ 加 $2_{(10)}$ 后个位满 $10$ 进一，结果为 $11_{(10)}$。

而二进制数仅有 $0$ 和 $1$，进位规则为「逢二进一」。例如：

1. $1_{(2)} + 0_{(2)} = 1_{(2)}$：$1_{(2)}$ 加 $0_{(2)}$ 得 $1_{(2)}$。
2. $1_{(2)} + 1_{(2)} = 10_{(2)}$：$1_{(2)}$ 加 $1_{(2)}$，满 $2$ 进一，结果为 $10_{(2)}$。
3. $10_{(2)} + 1_{(2)} = 11_{(2)}$：$10_{(2)}$ 加 $1_{(2)}$ 得 $11_{(2)}$。

1.2 二进制与十进制的相互转换

1.2.1 二进制转十进制

将二进制数转为十进制，就是将每一位上的数字乘以对应的 $2$ 的幂次，然后相加。例如：十进制 $2749_{(10)}$ 展开为 $2 \times 10^3 + 7 \times 10^2 + 4 \times 10^1 + 9 \times 10^0 = 2000 + 700 + 40 + 9 = 2749$。

同理，在二进制数中，$01101010_{(2)}$ 展开为 $0 \times 2^7 + 1 \times 2^6 + 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 0 + 64 + 32 + 0 + 8 + 0 + 2 + 0 = 106_{(10)}$。

二进制数转十进制数

我们可以通过这样的方式，将一个二进制数转为十进制数。

1.2.2 十进制转二进制

十进制转二进制常用方法是「除2取余，逆序排列」。

以 $106_{(10)}$ 为例：

1. $106 \div 2 = 53$，余 $0$。
2. $53 \div 2 = 26$，余 $1$。
3. $26 \div 2 = 13$，余 $0$。
4. $13 \div 2 = 6$，余 $1$。
5. $6 \div 2 = 3$，余 $0$。
6. $3 \div 2 = 1$，余 $1$。
7. $1 \div 2 = 0$，余 $1$。
8. $0 \div 2 = 0$，余 $0$。

将余数逆序排列，得到 $01101010_{(2)}$。

简而言之：不断除以 2，记录余数，最后将余数逆序排列即可得到二进制表示。

2. 位运算基础操作

基于二进制表示，我们可以对数字进行多种位运算。常见的位运算包括 $6$ 种：「按位与」、「按位或」、「按位异或」、「取反」、「左移」和「右移」。

其中，「按位与」、「按位或」、「按位异或」、「左移」、「右移」属于双目运算（需要两个操作数）：

• 「按位与」、「按位或」、「按位异或」：将两个整数转为二进制后，对应位逐一进行运算。
• 「左移」、「右移」：左侧为待移位的整数，右侧为移动的位数，对左侧二进制的所有位整体移动指定次数。

「取反」属于单目运算（只需一个操作数），即对一个整数的每一位进行取反操作。

下面先简要介绍这 $6$ 种位运算的基本规则，后续将逐一详细讲解。

运算符	描述	规则说明
|	按位或	只要对应的两个二进位中有一个为 $1$，结果位即为 $1$，否则为 $0$。
&	按位与	仅当对应的两个二进位都为 $1$ 时，结果位才为 $1$，否则为 $0$。
^	按位异或	对应的两个二进位不同则结果位为 $1$，相同则为 $0$。
~	按位取反	对操作数的每一位取反，$1$ 变为 $0$，$0$ 变为 $1$。
<<	左移	所有二进位整体向左移动指定的位数，高位溢出丢弃，低位补 $0$。
>>	右移	所有二进位整体向右移动指定的位数，低位溢出丢弃，高位补 $0$（无符号右移时）。

2.1 按位与运算

按位与运算（AND）：使用运算符 &，对两个二进制数的每一位进行比较，只有当对应位都为 $1$ 时，结果位才为 $1$，否则为 $0$。

• 按位与运算规则：
  • 1 & 1 = 1
  • 1 & 0 = 0
  • 0 & 1 = 0
  • 0 & 0 = 0

例如，将 $01111100_{(2)}$ 与 $00111110_{(2)}$ 进行按位与运算，结果为 $00111100_{(2)}$，如下图所示：

按位与运算

2.2 按位或运算

按位或运算（OR）：使用运算符 |，对两个二进制数的每一位进行「或」操作。只要对应的两个二进位中有一个为 $1$，结果位就是 $1$，只有两个都是 $0$ 时结果才为 $0$。

• 按位或运算规则：
  • 1 | 1 = 1
  • 1 | 0 = 1
  • 0 | 1 = 1
  • 0 | 0 = 0

例如，将 $01001010_{(2)}$ 与 $01011011_{(2)}$ 进行按位或运算，结果为 $01011011_{(2)}$，如下图所示：

按位或运算

2.3 按位异或运算

按位异或运算（XOR）：使用运算符 ^，对两个二进制数的每一位进行比较。只有当对应的两位不同（即一位为 $1$，一位为 $0$）时，结果位才为 $1$，否则为 $0$。

• 按位异或运算运算规则：
  • 0 ^ 0 = 0
  • 1 ^ 0 = 1
  • 0 ^ 1 = 1
  • 1 ^ 1 = 0

简而言之，异或运算的本质是「相同为 $0$，不同为 $1$」。

例如，将 $01001010_{(2)}$ 与 $01000101_{(2)}$ 进行按位异或运算，结果为 $00001111_{(2)}$，如下图所示：

按位异或运算

2.4 取反运算

取反运算（NOT）：取反运算符为 ~，用于将一个二进制数的每一位进行翻转，即 $1$ 变为 $0$，$0$ 变为 $1$。

• 取反运算规则：
  • ~0 = 1
  • ~1 = 0

例如，对二进制数 $01101010_{(2)}$ 进行取反，结果如下图所示：

取反运算

2.5 左移运算与右移运算

左移运算（SHL）：使用运算符 <<，将一个二进制数的所有位整体向左移动指定的位数。左移时，高位超出部分被舍弃，低位空缺部分补 $0$。

例如，将二进制数 $01101010_{(2)}$ 左移 $1$ 位，得到 $11010100_{(2)}$，如下图所示：

左移运算

右移运算（SHR）：使用运算符 >>，将一个二进制数的所有位整体向右移动指定的位数。右移时，低位超出部分被舍弃，高位空缺部分补 $0$。

例如，将二进制数 $01101010_{(2)}$ 右移 $1$ 位，得到 $00110101_{(2)}$，如下图所示：

右移运算

3. 位运算的应用

3.1 判断整数奇偶

判断一个整数的奇偶性，可以利用其二进制表示的最低位。偶数的二进制最低位为 $0$，奇数的最低位为 $1$。因此，通过将该数与 $1$ 进行按位与运算即可快速判断：

• 如果 (x & 1) == 0，则 $x$ 为偶数；
• 如果 (x & 1) == 1，则 $x$ 为奇数。

3.2 二进制数选取指定位

若需从二进制数 $X$ 中提取指定的若干位（即保留这些位的原值，其余位置为 $0$），可以先构造一个掩码 $Y$，使得需要保留的位置为 $1$，其余为 $0$。随后通过按位与运算（X & Y）即可实现目标。

例如，如果要获取 $X = 01101010_{(2)}$ 的最低 $4$ 位，只需将其与 $Y = 00001111_{(2)}$（最低 $4$ 位为 $1$，其余为 $0$）进行按位与运算：01101010 & 00001111 = 00001010。结果 $00001010$ 即为 $X$ 的末尾 $4$ 位。

3.3 将指定位设置为 $1$

若需将二进制数 $X$ 的某几位强制设置为 $1$（其余位保持原值），可构造一个掩码 $Y$，使得需要设置为 $1$ 的位为 $1$，其余为 $0$。然后通过按位或运算（X | Y）即可实现。

例如，若要将 $X = 01101010_{(2)}$ 的最低 $4$ 位设置为 $1$，其余位不变，只需与 $Y = 00001111_{(2)}$（最低 $4$ 位为 $1$，其余为 $0$）进行按位或运算：01101010 | 00001111 = 01101111。结果 $01101111$ 即为所需的新数。

3.4 反转指定位

若需反转二进制数 $X$ 的某几位，可构造一个掩码 $Y$，使得需要反转的位置为 $1$，其余为 $0$。然后对 $X$ 和 $Y$ 进行按位异或运算（X ^ Y），即可实现指定位的反转。

例如，若要反转 $X = 01101010_{(2)}$ 的最低 $4$ 位，只需将其与 $Y = 00001111_{(2)}$（最低 $4$ 位为 $1$，其余为 $0$）进行异或：01101010 ^ 00001111 = 01100101。结果 $01100101$ 即为 $X$ 的最低 $4$ 位被反转后的新值。

3.5 交换两个数

通过按位异或运算，可以无需临时变量实现两个整数的交换（仅适用于整数类型）。示例代码如下：

a, b = 10, 20
a ^= b
b ^= a
a ^= b
print(a, b)

3.6 将二进制最右侧为 $1$ 的二进位改为 $0$

要将二进制数 $X$ 最右侧的 $1$ 置为 $0$，只需执行 X & (X - 1) 操作即可。

例如，$X = 01101100_{(2)}$，$X - 1 = 01101011_{(2)}$，则 X & (X - 1) = 01101100 & 01101011 = 01101000，结果为 $01101000_{(2)}$，即成功将 $X$ 最右侧的 $1$ 变为 $0$。

3.7 计算二进制中二进位为 $1$ 的个数

根据 3.6 节的内容，利用 X & (X - 1) 操作可以将二进制数 $X$ 的最右侧一个 $1$ 变为 $0$。因此，如果我们不断对 $X$ 执行该操作，直到 $X$ 变为 $0$，并统计操作次数，就能得到 $X$ 的二进制表示中 $1$ 的个数。

实现代码如下：

class Solution:
    def hammingWeight(self, n: int) -> int:
        cnt = 0
        while n:
            n = n & (n - 1)
            cnt += 1
        return cnt

3.8 判断某数是否为 $2$ 的幂次方

判断一个数 $X$ 是否为 $2$ 的幂，可以利用位运算：只需判断 X & (X - 1) == 0 是否成立。

原理如下：

• 如果 $X$ 是 $2$ 的幂，则其二进制表示只有一位为 $1$，其余全为 $0$，如 $4_{(10)} = 00000100_{(2)}$，$8_{(10)} = 00001000_{(2)}$。
• 如果 $X$ 不是 $2$ 的幂，则其二进制表示中有多位为 $1$，如 $5_{(10)} = 00000101_{(2)}$，$6_{(10)} = 00000110_{(2)}$。

当 $X > 0$ 时，X & (X - 1) 的作用是将 $X$ 最右侧的 $1$ 变为 $0$，其余位保持不变：

• 如果 $X$ 是 $2$ 的幂，执行 X & (X - 1) 后结果为 $0$。
• 如果 $X$ 不是 $2$ 的幂，执行后结果不为 $0$。

因此，只需判断 X > 0 且 X & (X - 1) == 0，即可确定 $X$ 是否为 $2$ 的幂。

3.9 位运算的常用操作总结

序号	操作描述	位运算表达式	示例
1	从右边开始，把最后一个 $1$ 改写成 $0$	x & (x - 1)	100101000 -> 100100000
2	保留最右侧的 $1$，其余清零	x & -x 或 x & (x ^ (x - 1))	100101000 -> 1000
3	去掉最后一位	x >> 1	101101 -> 10110
4	取右数第 $k$ 位	(x >> (k - 1)) & 1	1101101 -> 1, k = 4
5	取末尾 $k$ 位	x & ((1 << k) - 1)	1101101 -> 101, k = 3； 1101101 -> 1101, k = 4
6	只保留右边连续的 $1$	(x ^ (x + 1)) >> 1	100101111 -> 1111
7	右数第 $k$ 位取反	x ^ (1 << (k - 1))	101001 -> 101101, k = 3
8	在最后加一个 $0$	x << 1	101101 -> 1011010
9	在最后加一个 $1$	(x << 1) + 1	101101 -> 1011011
10	把右数第 $k$ 位变成 $0$	x & ~(1 << (k - 1))	101101 -> 101001, k = 3
11	把右数第 $k$ 位变成 $1$	x | (1 << (k - 1))	101001 -> 101101, k = 3
12	把右边起第一个 $0$ 变成 $1$	x | (x + 1)	100101111 -> 100111111
13	把右边连续的 $0$ 变成 $1$	x | (x - 1)	11011000 -> 11011111
14	把右边连续的 $1$ 变成 $0$	x & (x + 1)	100101111 -> 100100000
15	把最后一位变成 $0$	x & ~1	101101 -> 101100
16	把最后一位变成 $1$	x | 1	101100 -> 101101
17	把末尾 $k$ 位变成 $1$	x | ((1 << k) - 1)	101001 -> 101111, k = 4
18	末尾 $k$ 位取反	x ^ ((1 << k) - 1)	101101 -> 101100, k = 1； 101001 -> 100110, k = 4

3.3 二进制枚举子集

在位运算中，常常利用二进制的第 $1 \sim n$ 位上的 $0$ 或 $1$ 来表示由 $1 \sim n$ 组成的集合，从而实现对子集的高效枚举。

3.3.1 二进制枚举子集简介

首先，简要介绍一下「子集」的定义：

• 子集：如果集合 $A$ 的所有元素均属于集合 $S$，则称 $A$ 是 $S$ 的子集，记作 $A \subseteq S$。

实际问题中，常常需要枚举集合 $S$ 的所有子集。枚举子集的方法有多种，这里介绍一种简洁高效的方式：「二进制枚举子集」。

对于一个包含 $n$ 个元素的集合 $S$，每个元素都有「选」或「不选」两种状态。我们可以用二进制数的 $n$ 位来表示每个元素的选取情况：$1$ 表示选取该元素，$0$ 表示不选取。

这样，任意一个 $n$ 位二进制数都唯一对应 $S$ 的一个子集。二进制的每一位对应集合中某个元素，$1$ 代表选取，$0$ 代表不选。

举例说明，设 $S = \lbrace 5, 4, 3, 2, 1 \rbrace$，用 $5$ 位二进制数表示：

• $11111_{(2)}$ 表示选取所有元素，即 $S$ 本身：

元素位置	5	4	3	2	1
二进制位	1	1	1	1	1
选取状态	选取	选取	选取	选取	选取

• $10101_{(2)}$ 表示选取第 $1$、$3$、$5$ 位元素，即 $\lbrace 5, 3, 1 \rbrace$：

元素位置	5	4	3	2	1
二进制位	1	0	1	0	1
选取状态	选取	未选取	选取	未选取	选取

• $01001_{(2)}$ 表示选取第 $1$、$4$ 位元素，即 $\lbrace 4, 1 \rbrace$：

元素位置	5	4	3	2	1
二进制位	0	1	0	0	1
选取状态	未选取	选取	未选取	未选取	选取

综上所述，对于长度为 $n$ 的集合 $S$，只需枚举 $0 \sim 2^n - 1$（共 $2^n$ 种 $n$ 位二进制数），即可高效遍历并生成 $S$ 的所有子集。

3.3.2 二进制枚举子集的实现代码

class Solution:
    def subsets(self, S):                           # 返回集合 S 的所有子集
        n = len(S)                                  # n 为集合 S 的元素个数
        sub_sets = []                               # sub_sets 用于保存所有子集
        for i in range(1 << n):                     # 枚举 0 ~ 2^n - 1 的所有可能，每个 i 表示一种选取方案
            sub_set = []                            # sub_set 用于保存当前子集
            for j in range(n):                      # 枚举集合 S 的每一个元素
                # (i >> j) & 1 判断第 j 位是否为 1
                # 如果为 1，说明在当前子集方案 i 中选取了 S[j]
                if (i >> j) & 1:                    # 如果第 j 位为 1，则选取 S[j]
                    sub_set.append(S[j])            # 将选取的元素 S[j] 加入到当前子集 sub_set 中
            sub_sets.append(sub_set)                # 将当前子集 sub_set 加入到所有子集数组 sub_sets 中
        return sub_sets                             # 返回所有子集

4. 总结

位运算是一种直接操作二进制位的高效技巧，能够在底层实现中大幅提升算法的时间和空间效率，广泛应用于状态压缩、集合枚举、掩码处理等场景。

位运算基础操作包括按位与、或、异或、取反、左移和右移等，这些操作能够直接高效地处理二进制数据，常用于状态压缩、集合枚举和性能优化等场景。

在实际应用中，常通过二进制状态来表示集合的选取情况，从而高效枚举所有子集。其核心思想是：用 $n$ 位二进制数的每一位对应集合中的一个元素，$1$ 表示选中该元素，$0$ 表示未选中。只需遍历 $0$ 到 $2^n-1$ 的所有二进制数，即可快速生成集合的全部子集。

练习题目

• 0190. 颠倒二进制位

• 0191. 位1的个数

• 0201. 数字范围按位与

• 0136. 只出现一次的数字

• 0137. 只出现一次的数字 II

• 0260. 只出现一次的数字 III

• 位运算题目列表

参考资料

• 【博文】Python 中的按位运算符 |【生长吧！Python!】- 云社区 - 华为云
• 【博文】一文读懂位运算的使用 - 小黑说 Java - 掘金
• 【博文】枚举排列和枚举子集 - CUC ACM-Wiki
• 【博文】Swift 运算符 | 菜鸟教程