位运算技巧
位运算是计算机底层最基础的操作之一，也是 LeetCode 高频考点。与常规的加减乘除不同，位运算直接对整数的二进制位进行操作，具有 O(1) 时间复杂度的天然优势。掌握位运算不仅能在面试中写出更优雅的解法，更能体现对计算机系统底层的理解深度。
本模块精选三道位运算相关的经典题目，覆盖三个核心技巧：异或消同（136）、摩尔投票（169）、Brian Kernighan 逐位消除（461）。这三道题虽然都标注为「简单」，但它们分别代表了位运算在"消去重复"、"统计计数"、"位差度量"三个维度的典型应用模式。
位运算核心速查：
| 运算 | 符号 | 含义 | 关键性质 |
|---|---|---|---|
| 与 | & | 两位都为1结果才为1 | n & (n-1) 消除最右边的1 |
| 或 | | | 至少一位为1结果就为1 | 常用于设置位 |
| 异或 | ^ | 相同为0，不同为1 | 自反性、交换律、结合律 |
| 左移 | << | 二进制位左移，相当于×2 | 高效乘法 |
| 右移 | >> | 二进制位右移，相当于÷2 | 高效除法 |
136. 只出现一次的数字 | 简单
标签: 位运算
题目描述：给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例：
输入：nums = [2,2,1]
输出：1
输入：nums = [4,1,2,1,2]
输出：4思路分析：这道题的突破口在于「其余每个元素均出现两次」这个特殊条件，它天然暗示了异或（XOR）运算。异或的核心性质有三条：(1) a ^ a = 0——任何数与自身异或结果为零；(2) a ^ 0 = a——任何数与零异或结果不变；(3) 异或满足交换律和结合律。基于这三条性质，将数组中所有元素依次异或，出现两次的数会两两抵消为 0，最终结果就是那个只出现一次的数。例如 [4,1,2,1,2] → 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for num in nums:
result ^= num
return result复杂度：时间 O(n)，空间 O(1)
169. 多数元素 | 简单
标签: 数组, 哈希表, Boyer-Moore投票算法
题目描述：给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例：
输入：nums = [3, 2, 3]
输出：3
输入：nums = [2, 2, 1, 1, 1, 2, 2]
输出：2思路分析：这道题最直接的思路是用哈希表计数，但进阶要求 O(1) 空间复杂度。Boyer-Moore 投票算法是此题的最优解——核心思想类似异或的"配对抵消"：维护一个候选者 candidate 和计数器 count。遍历数组时，若 count == 0 则更换候选者为当前元素；若当前元素等于候选者则 count + 1，否则 count - 1。直觉理解：把多数元素看成一个阵营，其他所有元素看成一个阵营，多数元素的票数严格超过半数，因此即使过程中被其他元素"抵消"掉一些票，最终剩下的候选者一定是多数元素。这种"不同则抵消"的思想与异或消去成对元素如出一辙。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate, count = 0, 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate复杂度：时间 O(n)，空间 O(1)
461. 汉明距离 | 简单
标签: 位运算
题目描述：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
输入：x = 3, y = 1
输出：1思路分析：汉明距离问题分两步走。第一步，异或：x ^ y 会将两个数中不同的位标记为 1、相同的位标记为 0，因此问题转化为「统计异或结果中 1 的个数」。第二步，统计 1 的个数：最朴素的方法是逐位右移检查，但更优雅的做法是 Brian Kernighan 算法——核心操作 n & (n - 1) 每次执行都会把 n 的二进制表示中最右边的 1 变成 0。原理在于：n - 1 会将最右边的 1 及其之后的所有位全部取反，再与原数做与运算，恰好消去最右边的 1。因此循环执行该操作直到 n 变为 0，执行次数就是 1 的个数。相比逐位检查的 O(log n)，Brian Kernighan 只需 O(k)（k 为 1 的个数），在 1 较少时效率更高。
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
xor = x ^ y
distance = 0
while xor:
xor &= xor - 1 # Brian Kernighan: 消除最右边的1
distance += 1
return distance复杂度：时间 O(1)（最多 31 次循环），空间 O(1)