LeetCode-Go 位运算（Bit Manipulation）专题模板解析：异或特性、Mask 构造与经典题解

本指南以 Bit_Manipulation.md 专题模板为核心，系统梳理 LeetCode-Go 仓库中位运算解题的核心知识体系：异或运算的五大特性、7 条特殊 Mask 构造公式，以及有特殊意义的 & 位操作，并结合仓库内 0136.Single-Number、0268.Missing-Number、0389.Find-the-Difference、0421.Maximum-XOR-of-Two-Numbers-in-an-Array、0260.Single-Number-III 等真实题解源码逐条印证。读完本篇，你将掌握位运算在「去重、找缺失、取特定位」三类高频场景下的推导方法与可复用的 Go 代码范式。

一、模板的定位：ctl 专题文档的生成骨架

在 LeetCode-Go 仓库中，ctl/ 目录是一个用于维护题解文档的 CLI 工具，而 ctl/template/ 下存放着按算法专题划分的 Markdown 模板，Bit_Manipulation.md 正是其中的位运算专题模板。

该模板的结构非常有代表性：

• 头部 front matter：声明 title: 2.15 ✅ Bit Manipulation，表明它是整个题解知识体系中编号为 2.15 的专题章节；
• 正文主体：以三段浓缩的「公式块」承载位运算专题的三大核心知识——异或特性、Mask 构造、特殊 & 操作；
• 尾部占位符：{{.AvailableTagTable}} 是 Go 模板变量，由 ctl 工具渲染时动态替换为「该专题下所有题目」的汇总表格，这正是每个专题目录下 README 中题目列表的来源。

换句话说，这份模板不仅是给读者看的速查卡，也是整个仓库位运算专题文档的「内容契约」：模板中出现的每一道题号，都对应 leetcode/ 下真实存在的一份题解目录。

二、异或（XOR）的五大特性：去重与找缺失的万能钥匙

模板首先给出异或运算的五个核心恒等式，这是位运算解题中最先要内化的内容：

x ^ 0 = x
x ^ 11111……1111 = ~x
x ^ (~x) = 11111……1111
x ^ x = 0
a ^ b = c  => a ^ c = b  => b ^ c = a (交换律)
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c (结合律)

其中三条性质直接决定了位运算在「配对消除」问题中的统治地位：

1. x ^ 0 = x 与 x ^ x = 0 的组合：同一数字异或两次会相互抵消。利用这一点，把数组中所有元素全部异或一遍，出现偶数次的数字全部归零，剩下的就是唯一出现奇数次的数字；
2. 交换律与结合律：异或结果与运算顺序无关，允许我们自由调整分组，这是很多「分治 + 异或」算法成立的前提；
3. a ^ b = c 的逆运算形式 a ^ c = b：知道两个数就能反推第三个，被广泛用于「通过异或和反查缺失项」以及贪心构造最大异或值。

2.1 特性应用一：136. Single Number（出现一次的数）

模板中列出的第一道题 136. Single Number，是「x ^ x = 0」最直接的体现。仓库题解 136. Single Number.go 的实现只有几行：

func singleNumber(nums []int) int {
	result := 0
	for i := 0; i < len(nums); i++ {
		result ^= nums[i]
	}
	return result
}

思路：数组里其他数字都出现两次，异或后相互抵消归零；而 x ^ 0 = x，最终 result 恰好保留那个只出现一次的数字。整段代码不使用任何额外空间，时间复杂度 O(n)，是位运算代替哈希表计数器的经典示范。

2.2 特性应用二：268. Missing Number（缺失的数字）

模板中第二道题 268. Missing Number，要求找出 [0, n] 范围内缺失的那个数。仓库实现 268. Missing Number.go 巧妙地把「下标」也纳入异或：

func missingNumber(nums []int) int {
	xor, i := 0, 0
	for i = 0; i < len(nums); i++ {
		xor = xor ^ i ^ nums[i]
	}
	return xor ^ i
}

思路：完整序列 0..n 中的每个数 i 与数组中的 nums[i] 逐一异或。凡是在数组中存在的数字，都会与它的下标成对抵消；唯一「只有下标、没有对应值」的那个 i，就是缺失的数字，最终通过 xor ^ i 取回。

2.3 特性应用三：389. Find the Difference（找差异字符）

模板中第三道题 389. Find the Difference 是异或在字符串场景的延伸：t 由 s 重排后多出一个字符。仓库实现 389. Find the Difference.go 同样用累计异或解决：

func findTheDifference(s string, t string) byte {
	n, ch := len(t), t[len(t)-1]
	for i := 0; i < n-1; i++ {
		ch ^= s[i]
		ch ^= t[i]
	}
	return ch
}

思路：s 与 t 中成对的字符全部抵消，多出的那一个字符（先以 t 末位字符作为种子）自然留存。这道题证明异或不仅能处理数字，也能逐字节处理字符串。

三、构造特殊 Mask：7 条位提取与位修改公式

模板第二部分给出位运算的另一类核心技能——用 Mask（掩码）精确控制二进制位。这 7 条公式覆盖了「清零、取值、置位」的全部基本操作：

将 x 最右边的 n 位清零，          x & ( ~0 << n )
获取 x 的第 n 位值(0 或者 1)，     (x >> n) & 1
获取 x 的第 n 位的幂值，           x & (1 << (n - 1))
仅将第 n 位置为 1，               x | (1 << n)
仅将第 n 位置为 0，               x & (~(1 << n))
将 x 最高位至第 n 位(含)清零，     x & ((1 << n) - 1)
将第 n 位至第 0 位(含)清零，      x & (~((1 << (n + 1)) - 1))

逐条解读它们的构造思路：

• ~0 是全 1，~0 << n 把低 n 位变成 0，与 x 相与即可把最右边 n 位清零；
• 右移 n 位后取最低位 & 1，即可读取第 n 位是 0 还是 1；
• 1 << (n-1) 是在第 n 位上构造出唯一的 1，与 x 相与得到该位的「幂值」；
• 置 1 用「或」：x | (1 << n) 保证第 n 位变 1 且不影响其他位；
• 置 0 用「与非」：~(1 << n) 把第 n 位变成 0、其余位全是 1，与 x 相与即可；
• (1 << n) - 1 产生低 n 位全 1 的 Mask，用于保留低位、清零高位；~((1 << (n+1)) - 1) 则相反，用于清零低 n+1 位。

3.1 Mask 思想的实战：421. Maximum XOR of Two Numbers in an Array

模板将 421. Maximum XOR of Two Numbers in an Array 列为异或专题的代表题。仓库的 421. Maximum XOR of Two Numbers in an Array.go 给出了一个把「Mask + 贪心 + 异或交换律」三者融合的漂亮解法：

func findMaximumXOR(nums []int) int {
	maxResult, mask := 0, 0
	for i := 31; i >= 0; i-- {
		// mask 从 100..000 逐步增长为 1111...111
		mask = mask | (1 << uint(i))
		m := make(map[int]bool)
		for _, num := range nums {
			m[num&mask] = true
		}
		greedyTry := maxResult | (1 << uint(i))
		for anotherNum := range m {
			// 关键：若 a ^ b = c，则 a ^ c = b
			if m[anotherNum^greedyTry] == true {
				maxResult = greedyTry
				break
			}
		}
	}
	return maxResult
}

这段代码与模板的两处知识一一对应：

• Mask 逐步构造：mask = mask | (1 << i) 从最高位开始逐位累积，每轮只保留数字的高位部分（num & mask），这与模板中「构造特殊 Mask，将特殊位置放 0 或 1」的思想完全一致；
• 异或交换律反查：想验证某一位能否取到 1，先假定 greedyTry 是答案，再用 anotherNum ^ greedyTry 反查配对数字是否存在于集合中——正是模板公式 a ^ b = c => a ^ c = b 的直接应用。

3.2 取最低位 1：260. Single Number III（两个只出现一次的数）

模板把 260. Single Number III 归入「有特殊意义的 & 位操作」分类。题目是 136 题的进阶版：数组中有两个数只出现一次，其余都出现两次。仓库实现 260. Single Number III.go 的解法分为三步：

func singleNumberIII(nums []int) []int {
	diff := 0
	for _, num := range nums {
		diff ^= num
	}
	// 取 diff 最低位的 1，用于分组
	diff &= -diff
	res := []int{0, 0}
	for _, num := range nums {
		if (num & diff) == 0 { // 该位为 0 的一组
			res[0] ^= num
		} else { // 该位为 1 的一组
			res[1] ^= num
		}
	}
	return res
}

思路拆解：

1. 全体异或后，diff = a ^ b（两个目标数字的异或值），其余数对全部抵消；
2. diff &= -diff 取出 diff 最低位的 1——这是 a 与 b 二进制表示中第一个不同的位，正是模板中「X & -X 得到最低位（LSB）的 1」的公式应用；
3. 以该位为分界，把原数组分成「该位为 0」与「该位为 1」两组，a、b 必然分居两组，组内再各自异或即可分别求出。

四、有特殊意义的 & 操作：四个高频恒等式

模板第三部分给出四个在复杂度优化中极具价值的位操作恒等式：

X & 1 == 1   判断是否是奇数(偶数)
X & = (X - 1)  将最低位(LSB)的 1 清零
X & -X         得到最低位(LSB)的 1
X & ~X = 0

逐条说明其用途：

• X & 1：仅保留最低位，用于 O(1) 判断奇偶，比取模运算更贴近底层语义；
• X & (X - 1)：把最低位的 1 清零。这是统计二进制中 1 的个数（如 191. Number of 1 Bits）的标准技巧——每次循环清除一个 1，循环次数即为 1 的个数；
• X & -X：-X 是 X 的补码（取反加一），两者相与恰好得到最低位 1 的幂值。除上文 260 题外，它也是树状数组（Binary Indexed Tree）lowbit 操作的核心，仓库 structures 目录中的相关实现可以佐证这一写法的通用性；
• X & ~X：一个数与自身的反码相与恒为 0，常用于构造全零结果或校验掩码的正确性。

模板同时将 201. Bitwise-AND-of-Numbers-Range、318. Maximum-Product-of-Word-Lengths、371. Sum-of-Two-Integers、397. Integer-Replacement、461. Hamming-Distance、693. Binary-Number-with-Alternating-Bits 等题归入该分类，它们分别从「区间与」「状态压缩」「无进位加法」「奇偶分支」「汉明距离」「交替位校验」等角度反复锤炼这些恒等式。

五、专题题目的仓库分布：一条可验证的刷题路线

模板中出现的每一道题，都能在 leetcode/ 目录下找到对应的题解与测试文件。整理如下，便于按图索骥：

专题分类	题目	仓库目录
异或特性	136. Single Number	leetcode/0136.Single-Number
异或特性	268. Missing Number	leetcode/0268.Missing-Number
异或特性	389. Find the Difference	leetcode/0389.Find-the-Difference
异或特性	421. Maximum XOR of Two Numbers in an Array	leetcode/0421.Maximum-XOR-of-Two-Numbers-in-an-Array
特殊 & 操作	260. Single Number III	leetcode/0260.Single-Number-III
特殊 & 操作	201. Bitwise AND of Numbers Range	leetcode/0201.Bitwise-AND-of-Numbers-Range
特殊 & 操作	318. Maximum Product of Word Lengths	leetcode/0318.Maximum-Product-of-Word-Lengths
特殊 & 操作	371. Sum of Two Integers	leetcode/0371.Sum-of-Two-Integers
特殊 & 操作	397. Integer Replacement	leetcode/0397.Integer-Replacement
特殊 & 操作	461. Hamming Distance	leetcode/0461.Hamming-Distance
特殊 & 操作	693. Binary Number with Alternating Bits	leetcode/0693.Binary-Number-with-Alternating-Bits

每个目录下均包含题解 .go 文件与对应的 _test.go 测试文件，例如 136. Single Number_test.go 覆盖了常规、负值、单元素等边界用例，可以用仓库根目录下的 gotest.sh 脚本统一运行验证。

六、如何在项目中使用这份模板

从源码结构看，ctl/ 目录下的渲染逻辑（render.go、template_render.go）负责将 ctl/template/ 中的专题模板与题库数据合并，把 {{.AvailableTagTable}} 这类占位符替换为实际的题目表格，最终生成各专题的 Markdown 文档。因此这份 Bit_Manipulation.md 的实用价值体现在两个层面：

1. 作为读者速查卡：三段公式本身就是位运算解题的最小知识集，刷题前通读一遍即可覆盖绝大多数位运算题的推导起点；
2. 作为文档生成的输入：模板中维护的题号清单，决定了该专题在站点文档中的目录结构与题目覆盖范围。

需要说明的是，模板头部引用的示例配图托管于外部图床，仓库内 topic/ 目录下的图片资源主要用于站点渲染；本文档核心的三段公式与题目映射均已通过上述仓库源码逐条验证，不依赖任何图片即可完整自洽。

总结

LeetCode-Go 仓库的位运算专题模板，用三组公式就勾勒出了位运算解题的全貌：异或五大特性解决去重与找缺失，7 条 Mask 公式解决特定位的读写与清零，4 个特殊 & 恒等式解决奇偶判断、最低位提取与计数问题。结合 136、268、389、421、260 五份源码可以发现：所有看似复杂的位运算题，最终都能回溯到这份模板中的某一条公式。把这三组公式内化为直觉，位运算题型便可迎刃而解。