代码随想录 — 位运算与数学技巧

补充专题：位运算在 LeetCode 中出现频率不高，但属于「技巧」类常考点，掌握核心操作即可应对面试。

---

一、位运算基础

运算	符号	说明	示例
与 AND	&	两位都为 1 结果为 1	5 & 3 = 1（101 & 011 = 001）
或 OR	|	有一位为 1 结果为 1	5 | 3 = 7（101 | 011 = 111）
异或 XOR	^	两位不同为 1	5 ^ 3 = 6（101 ^ 011 = 110）
取反 NOT	~	0 变 1，1 变 0	~5 = -6
左移	<<	乘以 2 的幂	3 << 2 = 12
右移	>>	除以 2 的幂	12 >> 2 = 3

核心性质（必记）

• n & (n - 1)：消除最低位的 1（Brian Kernighan）
• n & (-n)：获取最低位的 1
• a ^ a = 0，a ^ 0 = a：异或自消
• a ^ b ^ a = b：异或满足交换律和结合律

---

二、常见题目与思路

题目	思路要点	复杂度
136 只出现一次的数字 🟢	全部异或，成对的消掉，剩下的就是答案。	O(n) / O(1)
191 位 1 的个数 🟢	不断 n &= (n-1) 消除最低位 1，计数。	O(k)，k 为 1 的个数
231 2 的幂 🟢	n > 0 && (n & (n-1)) === 0，2 的幂只有一个 1。	O(1)
338 比特位计数 🟢	dp[i] = dp[i & (i-1)] + 1，利用消最低位 1。	O(n)
169 多数元素 🟢	Boyer-Moore 投票法（非位运算但属技巧）。	O(n) / O(1)
461 汉明距离 🟢	x ^ y 后数 1 的个数。	O(k)
268 丢失的数字 🟢	0~n 全部异或再异或数组，剩下的就是缺失的。或用求和。	O(n) / O(1)
287 寻找重复数 🟡	快慢指针（类似环形链表 142），不是位运算但属技巧。	O(n) / O(1)
260 只出现一次的数字 III 🟡	全部异或得 a^b，取最低位 1 分组，两组分别异或。	O(n) / O(1)

---

三、核心代码模板

只出现一次的数字（136）

// JavaScript — 时间 O(n)，空间 O(1)
function singleNumber(nums) {
  let res = 0;
  for (const num of nums) res ^= num;
  return res;
}

位 1 的个数（191）

// JavaScript — Brian Kernighan
function hammingWeight(n) {
  let count = 0;
  while (n) {
    n &= (n - 1); // 消除最低位的 1
    count++;
  }
  return count;
}

2 的幂（231）

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

比特位计数（338）

// JavaScript — 时间 O(n)
function countBits(n) {
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i & (i - 1)] + 1;
  }
  return dp;
}

多数元素 — Boyer-Moore 投票法（169）

// JavaScript — 时间 O(n)，空间 O(1)
function majorityElement(nums) {
  let candidate = nums[0], count = 1;
  for (let i = 1; i < nums.length; i++) {
    if (count === 0) { candidate = nums[i]; count = 1; }
    else if (nums[i] === candidate) count++;
    else count--;
  }
  return candidate;
}

# Python — 只出现一次的数字 III（260）
def single_number_iii(nums):
    xor_all = 0
    for num in nums:
        xor_all ^= num
    # 取最低位 1，用来分组
    lowest_bit = xor_all & (-xor_all)
    a, b = 0, 0
    for num in nums:
        if num & lowest_bit:
            a ^= num
        else:
            b ^= num
    return [a, b]

---

四、位运算技巧速查

操作	表达式	用途
判断奇偶	n & 1	1 为奇，0 为偶
除以 2	n >> 1	等价于 Math.floor(n/2)
乘以 2	n << 1
消最低位 1	n & (n-1)	计数 1 的个数、判断 2 的幂
取最低位 1	n & (-n)	分组（260）、树状数组
交换两数	a^=b; b^=a; a^=b	不用临时变量（了解即可）
取绝对值	(n ^ (n>>31)) - (n>>31)	32 位整数（了解即可）

建议：掌握异或的性质（136/268）和 n & (n-1) 技巧（191/231/338）即可应对大部分面试题。