位运算技巧

位运算是面试中的加分项。关键不是背技巧，而是理解位运算为什么能做某些事，以及这些技巧背后的原理。

面试考察点

面试官通过这道题想考察：
1. 你是否理解位运算的基本原理
2. 你是否能解释常见技巧的原理
3. 你是否能用位运算优化代码
4. 你是否理解补码表示

---

一、位运算基础

1.1 基本位运算符

面试官追问："位运算有哪些？"

| 运算符 | 名称 | 说明 |
|--------|------|------|
| &      | 与   | 两位都为1时结果为1 |
| |      | 或   | 任一位为1时结果为1 |
| ^      | 异或 | 两位不同时结果为1 |
| ~      | 取反 | 0变1，1变0 |
| <<     | 左移 | 二进制左移，低位补0 |
| >>     | 右移 | 二进制右移，高位补符号位 |

示例：
a = 60 = 00111100
b = 13 = 00001101

a & b = 00001100 = 12
a | b = 00111101 = 61
a ^ b = 00110001 = 49
~a   = 11000011 = -61（补码表示）
a << 2 = 11110000 = 240
a >> 2 = 00001111 = 15

1.2 异或的妙用

面试官追问："异或有什么特殊的性质？"

异或的三个性质：

1. a ^ a = 0
   任何数和自身异或都等于 0

2. a ^ 0 = a
   任何数和 0 异或都等于自身

3. 异或满足交换律和结合律
   a ^ b ^ c = a ^ c ^ b = ...

应用 1：交换两个数

a = a ^ b
b = a ^ b  # 此时 a = a ^ b，b = (a ^ b) ^ b = a
a = a ^ b  # 此时 b = a，a = (a ^ b) ^ a = b

应用 2：找出现奇数次的数

数组中只有一个数出现奇数次，其他都出现偶数次
所有数异或，结果就是那个数！

原理：成对的数异或都变成 0
      最后剩下 0 ^ 目标数 = 目标数

---

二、常见位运算技巧

2.1 判断奇偶

n & 1 == 1 → n 是奇数
n & 1 == 0 → n 是偶数

原理：奇数二进制最后一位是 1

比 n % 2 更快！

2.2 获取/清除/设置某一位

获取第 i 位：
(n >> i) & 1

设置第 i 位为 1：
n | (1 << i)

清除第 i 位为 0：
n & ~(1 << i)

切换第 i 位：
n ^ (1 << i)

2.3 清除最低位的 1

面试官追问："n & (n-1) 是什么意思？"

n & (n-1) 清除 n 二进制表示中最低位的 1

示例：
n = 12 = 1100
n-1 = 11 = 1011
n & (n-1) = 1000 = 8

为什么？

n =     1 1 0 0
n-1 =   1 0 1 1
n&(n-1) = 1 0 0 0

最低位的 1 变成 0，后面的都变成 1 再 AND 1
所以结果就是最低位的 1 被清除！

应用：统计 1 的个数

def countOnes(n):
    count = 0
    while n:
        n = n & (n-1)  # 清除最低位的 1
        count += 1
    return count

每次清除一个 1，有多少个 1 就循环多少次！

---

三、算法应用

3.1 缺失数字（LeetCode 268）

考察点：异或的应用

问题：0到n中缺失了一个数字

思路：
结果 = 0 ^ 1 ^ 2 ^ ... ^ n ^ nums[0] ^ nums[1] ^ ...
     = 缺失的数字（其他数字都出现两次，异或为0）

代码：
result = len(nums)
for i, num in enumerate(nums):
    result ^= i ^ num
return result

3.2 只出现一次的数字（LeetCode 136）

考察点：异或的应用

问题：除一个数字外，其他数字都出现两次

所有数字异或：
a ^ a ^ b ^ b ^ c ^ c ^ ... ^ target ^ ...
= 0 ^ target
= target

直接返回异或结果！

---

四、面试总结

位运算核心要点

┌─────────────────────────────────────────────────┐
│                  位运算核心                       │
├─────────────────────────────────────────────────┤
│                                                  │
│  常用技巧：                                      │
│  - n & 1：判断奇偶                               │
│  - n & (n-1)：清除最低位的 1                   │
│  - n & -n：获取最低位的 1                       │
│  - a ^ a = 0：异或消除成对的数                   │
│                                                  │
│  应用场景：                                      │
│  - 状态压缩                                     │
│  - 权限管理                                     │
│  - 快速计算                                     │
│                                                  │
└─────────────────────────────────────────────────┘

面试能加分的回答

1. 能解释 n & (n-1)
   "清除最低位的 1，因为 n-1 把最低位的 1 变成 0，
    后面的位都变成 1，AND 后就清除了"

2. 能解释异或的性质
   "a ^ a = 0，所以成对出现的数异或都消掉了"

3. 能指出位运算的优势
   "位运算是 O(1) 的，比乘除法快得多"

---

相关题目

• LeetCode 136 - 只出现一次的数字 - 异或应用
• LeetCode 338 - 比特位计数 - 位运算应用