AlgoNote 算法通关手册：位运算从入门到实战（二进制基础、六大运算符、掩码技巧与子集枚举）

• 教程
• 文档
• 知识库

导读

位运算是直接操作二进制位的高效技巧，在状态压缩、集合枚举、掩码处理与极致性能优化场景中扮演关键角色。本文以《AlgoNote 算法通关手册》中「位运算」章节为主体，系统讲解二进制与十进制的转换、按位与/或/异或/取反/左移/右移六大基础操作、18 种常用位运算技巧，并结合仓库内 0136、0191、0078 等 LeetCode 题解源码，给出可直接运行的实战代码。读完本文，你将掌握用一行位运算判断奇偶、统计二进制中 1 的个数、判断 2 的幂次方、用二进制枚举集合全部子集等核心能力。

1. 位运算与二进制基础

1.1 什么是位运算

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

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

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

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

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

• $1_{(2)} + 0_{(2)} = 1_{(2)}$：$1_{(2)}$ 加 $0_{(2)}$ 得 $1_{(2)}$。
• $1_{(2)} + 1_{(2)} = 10_{(2)}$：$1_{(2)}$ 加 $1_{(2)}$，满 $2$ 进一，结果为 $10_{(2)}$。
• $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$ 种：「按位与」「按位或」「按位异或」「取反」「左移」「右移」。其中「按位与」「按位或」「按位异或」「左移」「右移」属于双目运算（需要两个操作数）：

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

「取反」属于单目运算（只需一个操作数），即对一个整数的每一位进行取反操作。六种运算符规则汇总如下：

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)}$ 取反后每一位翻转，得到 $10010101_{(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)}$ 按位与：01101010 & 00001111 = 00001010，结果即为 $X$ 的末尾 $4$ 位。

3.3 将指定位设置为 1

如果需将二进制数 $X$ 的某几位强制设置为 $1$（其余位保持原值），可构造掩码 $Y$，使需要设置为 $1$ 的位为 $1$、其余为 $0$，再执行按位或运算（X | Y）。

例如，将 $X = 01101010_{(2)}$ 的最低 $4$ 位设置为 $1$：01101010 | 00001111 = 01101111。

3.4 反转指定位

如果需反转二进制数 $X$ 的某几位，可构造掩码 $Y$，使需要反转的位置为 $1$、其余为 $0$，然后执行按位异或运算（X ^ Y）。

例如，反转 $X = 01101010_{(2)}$ 的最低 $4$ 位：01101010 ^ 00001111 = 01100101。

3.5 交换两个数

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

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

原理依托异或运算的性质（详见第 4 节）：$a \oplus b$ 保存了两者的差异信息，连续三次异或即可完成互换。

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

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

例如，$X = 01101100_{(2)}$，$X - 1 = 01101011_{(2)}$，则X & (X - 1) = 01101100 & 01101011 = 01101000，成功将最右侧的 $1$ 变为 $0$。这一技巧在统计二进制中 $1$ 的个数、判断 $2$ 的幂次方（见 3.7、3.8）中反复使用。

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

根据 3.6 节，X & (X - 1)每次可将最右侧一个 $1$ 变为 $0$。因此不断执行该操作直到 $X$ 变为 $0$，操作次数即为 $1$ 的个数：

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

该实现对应 LeetCode 0191. 位1的个数。仓库题解中同时给出了循环按位统计的写法ans += (n & 1); n >>= 1，其时间复杂度为 $O(k)$（$k = 32$），而n & (n - 1)写法的执行次数仅与 $1$ 的个数相关，时间复杂度为 $O(\log n)$，空间复杂度均为 $O(1)$。

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$ 的幂则结果为 $0$，否则不为 $0$。因此，只需判断X > 0且X & (X - 1) == 0，即可确定 $X$ 是否为 $2$ 的幂。

3.9 位运算的常用操作总结

下表汇总了 18 种高频位运算表达式，是刷题与工程中可直接套用的「位运算速查表」：

4. 异或运算的性质与实战进阶

异或是位运算中最「神奇」的一种，在只出现一次的数字、数字范围按位与等题目中起着关键作用。仓库题解 0136. 只出现一次的数字 总结了异或运算的三个核心性质：

1. 任何数和 $0$ 做异或运算，结果仍然是原来的数，即 $a \oplus 0 = a$。
2. 数和其自身做异或运算，结果是 $0$，即 $a \oplus a = 0$。
3. 异或运算满足交换律和结合律：$a \oplus b \oplus a = b \oplus a \oplus a = b \oplus (a \oplus a) = b \oplus 0 = b$。

性质 3 是「找单数」题目的基石：对数组中全部元素连续异或，成对出现的数字两两抵消为 $0$，最终只剩出现一次的元素。以 0136. 只出现一次的数字 为例，题目要求不使用额外存储空间，异或解法完美满足 $O(n)$ 时间、$O(1)$ 空间：

class Solution: def singleNumber(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] ans = 0 for i in range(len(nums)): ans ^= nums[i] return ans

进阶：两个只出现一次的数字。0260. 只出现一次的数字 III 中数组恰好有两个元素只出现一次，其余均出现两次。解法分三步：

1. 全部异或得到两个目标数的异或结果all_xor；
2. 找出all_xor中最低位的 $1（两个数在该位必不相同），用mask` 定位分组依据；
3. 按该位是否为 $1` 将数组分为两组，分别异或即得两个答案：

class Solution: def singleNumbers(self, nums: List[int]) -> List[int]: all_xor = 0 for num in nums: all_xor ^= num # 获取所有异或中最低位的 1 mask = 1 while all_xor & mask == 0: mask <<= 1 a_xor, b_xor = 0, 0 for num in nums: if num & mask == 0: a_xor ^= num else: b_xor ^= num return a_xor, b_xor

再进阶：数字范围按位与。0201. 数字范围按位与 要求返回区间 $[left, right]$ 内所有数字按位与的结果。暴力枚举会超时，正确思路是借助n & (n - 1)不断清除right最右侧的 $1$，直到right不大于left，此时剩余部分即为公共前缀（后缀补 $0$）：

class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: while left < right: right = right & (right - 1) return right

该解法时间复杂度 $O(\log n)$、空间复杂度 $O(1)$，是 3.6 节技巧在区间问题中的经典延伸。

注意 Python 的负数补码陷阱。在 0137. 只出现一次的数字 II 的按位统计解法中，题解特别说明：Python 整数没有位数限制，负数的补码会被当作正整数处理，因此在遍历到第 $31$ 位时需执行ans -= (1 << 31)，把负数的补码转换为「负号 + 原码」形式，才能正确识别二进制下的负数。

5. 二进制枚举子集

5.1 二进制枚举子集简介

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

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

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

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

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

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

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

5.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 # 返回所有子集

该实现对应 LeetCode 0078. 子集 的思路二（二进制枚举）。仓库题解同时给出了回溯法（思路一）的对照实现，二者时间复杂度均为 $O(n \times 2^n)$，空间复杂度均为 $O(n)$——二进制枚举借助位运算省去了递归调用栈，在元素个数 $n \le 20$ 左右的场景下尤为简洁高效。

6. 位运算在其他模块中的落地

位运算并非孤立技巧，而是渗透在整个《AlgoNote 算法通关手册》的各个算法模块中：

• 状态压缩 DP：在 08_dynamic_programming 章节中，用二进制位表示集合状态、以1 << i表示选中第 $i$ 个元素、用(mask >> i) & 1探测状态，都是位运算的直接应用。
• 树状数组：在 05_07_binary_indexed_tree.md 及对应实现 tree_binaryindexed_tree.py 中，i & (-i)用于提取最低位 $1（lowbit），是维护前缀和的基石操作；i += i & (-i)与i -= i & (-i)` 分别驱动区间更新的向上与向下遍历。
• 数位 DP：在 08_15_digit_dp.md 及对应实现 Digit-DP.py 中，通过(x >> i) & 1逐位提取二进制状态、用1 << i构造掩码，配合x & (x - 1)快速枚举二进制数中 $1$ 的分布。
• 位运算题目合集：完整的位运算练习清单可在 00_06_categories_list.md 位运算题目列表 中按标签检索，涵盖 0136、0260、0421（数组中两个数的最大异或值，字典树 + 位运算）、1310（子数组异或查询，异或前缀和）等经典题目。

7. 总结

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

1. 六大基础操作：按位与（&）、按位或（|）、按位异或（^）、取反（~）、左移（<<）、右移（>>），配合第 3.9 节的 18 种常用表达式速查表，可以快速完成置位、清位、翻转、取位等一切掩码操作。
2. 两大万能公式：x & (x - 1)清除最右侧的 $1$（用于数 $1$ 个数、判断 $2$ 的幂、求区间公共前缀）；x & -x保留最右侧的 $1$（用于树状数组 lowbit、分组异或的 mask 构造）。
3. 一个枚举思想：用 $n$ 位二进制数的每一位对应集合中的一个元素，$1$ 表示选中、$0$ 表示未选中，遍历 $0$ 到 $2^n - 1$ 即可快速生成集合的全部子集。

练习题目

按由浅入深的顺序，建议依次完成以下位运算题目（题解均收录于本仓库）：

• 0190. 颠倒二进制位（逐位翻转：res = (res << 1) | (n & 1)）
• 0191. 位1的个数（n & (n - 1)计数）
• 0136. 只出现一次的数字（异或抵消）
• 0137. 只出现一次的数字 II（逐位统计 + 模 3，注意 Python 负数补码）
• 0260. 只出现一次的数字 III（异或 + 最低位 1 分组）
• 0201. 数字范围按位与（right & (right - 1)求公共前缀）

更多位运算题目可按标签在 00_06_categories_list.md 位运算题目列表 中持续练习。

• 教程
• 文档
• 知识库