位运算

一句话：位运算题的价值几乎都来自异或（XOR）的两条性质——自反性（a^a=0）让”找落单元素”不需要额外空间，无进位加法的特性让它能模拟加法。认出题目在利用哪一条，解法基本就出来了。

异或的自反性：找落单元素不需要哈希表

136-只出现一次的数字 是最直接的应用：数组里其他数字都出现两次，只有一个出现一次，把所有数字异或起来，成对的数字两两抵消为 0，剩下的就是答案——不需要哈希表统计次数，O(1) 空间完成。

260-只出现一次的数字III 是进阶版：两个数字只出现一次，直接全部异或只能得到这两个数的异或值。技巧是找到这个异或结果里任意一个为 1 的二进制位（说明这一位上两个目标数字不同），按这一位把所有数字分成两组，每组内部再异或一次，两个目标数字必然被分到不同组，组内的重复数字仍然两两抵消——用一次”按位分组”把问题降回到 136 的场景。

371-两整数之和 反过来利用异或模拟加法：异或等价于”不考虑进位的加法”，与运算左移一位等价于”进位”，不断把”无进位和”与”进位”相加直到进位变为 0，即完成了整个加法过程——这是用位运算绕开语言层面 + 运算符限制的经典技巧。

位掩码：用一个整数表示一个子集

78-子集 除了回溯的显式递归解法外，还有位运算解法：n 个元素的每个子集都能用一个 n 位的二进制数表示（第 i 位是 1 表示选中第 i 个元素），直接枚举 0 到 2^n - 1 的所有整数，对每个整数检查每一位即还原出一个子集——这把回溯的”递归遍历决策树”压平成了”遍历所有整数”，两者遍历的是同一个 2ⁿ 大小的搜索空间，只是用位运算省去了显式的递归调用栈。

338-比特位计数 要求对 0..n 每个数统计二进制中 1 的个数，暴力做法是对每个数单独数位，O(n log n)；更快的做法是利用递推关系 dp[i] = dp[i >> 1] + (i & 1)（i 右移一位后 1 的个数，加上被移掉的那一位是否为 1）——本质是动态规划，只是转移方程建立在位运算操作之上。

461-汉明距离 是 136 反问题的简化版：两个数的汉明距离就是它们异或结果里 1 的个数，直接复用统计 1 的个数的技巧（n & (n-1) 能每次消除最低位的 1，是比逐位检查更快的计数方式）。