位运算：在二进制世界里翩翩起舞

当别人还在用加减乘除时，你已经在用与或非异或了

什么是位运算

位运算（Bit Manipulation）是直接对整数在内存中的二进制位进行操作的运算方式。相比普通的算术运算，位运算在某些场景下速度更快、更节省空间。

核心特点：直接操作二进制位，效率极高

为什么要学位运算？

graph LR
    A[位运算的优势] --> B[速度快]
    A --> C[省空间]
    A --> D[技巧性强]
    A --> E[面试常考]
    
    B --> B1[CPU直接支持]
    C --> C1[用位表示状态]
    D --> D1[巧妙解决问题]
    E --> E1[考察基本功]
    
    style A fill:#FFE4B5
    style B fill:#90EE90
    style D fill:#87CEEB

基础位运算符

六大运算符

运算符 名称 说明 示例
& 按位与 两位都为1才为1 5 & 3 = 1
| 按位或 有一位为1就为1 5 | 3 = 7
^ 按位异或 相同为0，不同为1 5 ^ 3 = 6
~ 按位取反 0变1，1变0 ~5 = -6
<< 左移 向左移位，右边补0 5 << 1 = 10
>> 右移 向右移位，左边补符号位 5 >> 1 = 2

运算符详解

1. 按位与（&）

1
2
3
4
5
6
7
8
9
10
11
规则：两位都为1才为1

    5:  0101
  & 3:  0011
  ————————————
    1:  0001

应用：
- 判断奇偶：n & 1（最低位为1是奇数）
- 清零特定位
- 提取特定位

2. 按位或（|）

1
2
3
4
5
6
7
8
9
10
规则：有一位为1就为1

    5:  0101
  | 3:  0011
  ————————————
    7:  0111

应用：
- 设置特定位为1
- 合并标志位

3. 按位异或（^）★

1
2
3
4
5
6
7
8
9
10
11
12
规则：相同为0，不同为1

    5:  0101
  ^ 3:  0011
  ————————————
    6:  0110

神奇性质：
1. a ^ a = 0（自己异或自己等于0）
2. a ^ 0 = a（任何数异或0等于自己）
3. 交换律：a ^ b = b ^ a
4. 结合律：a ^ b ^ c = a ^ (b ^ c)

4. 按位取反（~）

1
2
3
4
5
规则：0变1，1变0

  ~5:  ~0101 = 1010（补码表示为-6）

注意：涉及到补码，负数表示

5. 左移（<<）

1
2
3
4
5
6
规则：向左移n位，相当于乘以2^n

5 << 1:  0101 << 1 = 1010 (10)
5 << 2:  0101 << 2 = 10100 (20)

规律：n << k = n * 2^k

6. 右移（>>）

1
2
3
4
5
6
规则：向右移n位，相当于除以2^n

5 >> 1:  0101 >> 1 = 0010 (2)
5 >> 2:  0101 >> 2 = 0001 (1)

规律：n >> k = n / 2^k（向下取整）

常见位运算技巧

1. 判断奇偶

1
2
3
4
5
6
// 传统方法
if (n % 2 == 0) { /* 偶数 */ }

// 位运算（更快）
if ((n & 1) == 0) { /* 偶数 */ }
if (n & 1) { /* 奇数 */ }

原理：二进制最低位为0是偶数，为1是奇数

1
2
4: 0100 & 1 = 0 (偶数)
5: 0101 & 1 = 1 (奇数)

2. 交换两个数（不用临时变量）

1
2
3
4
5
6
7
8
9
// 传统方法
int temp = a;
a = b;
b = temp;

// 位运算（无需临时变量）
a = a ^ b;
b = a ^ b;  // b = (a^b) ^ b = a
a = a ^ b;  // a = (a^b) ^ a = b

原理：利用异或的性质 a ^ b ^ b = a

3. 获取/设置/清除特定位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 获取第k位（从0开始）
int getBit(int n, int k) {
    return (n >> k) & 1;
}

// 设置第k位为1
int setBit(int n, int k) {
    return n | (1 << k);
}

// 清除第k位（设为0）
int clearBit(int n, int k) {
    return n & ~(1 << k);
}

// 切换第k位（0变1，1变0）
int toggleBit(int n, int k) {
    return n ^ (1 << k);
}

示例：

1
2
3
4
5
6
n = 5 (0101)

getBit(5, 2) = (0101 >> 2) & 1 = 01 & 1 = 1
setBit(5, 1) = 0101 | 0010 = 0111 = 7
clearBit(5, 0) = 0101 & ~0001 = 0101 & 1110 = 0100 = 4
toggleBit(5, 1) = 0101 ^ 0010 = 0111 = 7

4. 清除最低位的1

1
2
3
4
// 清除最右边的1
int clearLowestBit(int n) {
    return n & (n - 1);
}

原理图解：

1
2
3
4
n = 12:  1100
n-1 = 11: 1011
n & (n-1): 1100 & 1011 = 1000 = 8
         清除了最右边的1

应用：统计1的个数（Brian Kernighan算法）

5. 获取最低位的1

1
2
3
4
// 只保留最右边的1
int getLowestBit(int n) {
    return n & (-n);
}

原理：

1
2
3
n = 12:   0...01100
-n:       1...10100（补码）
n & (-n): 0...00100 = 4

应用：树状数组（Fenwick Tree）

6. 判断是否为2的幂

1
2
3
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

原理：2的幂只有一个1

1
2
3
4
2:  0010 & 0001 = 0000 ✓
4:  0100 & 0011 = 0000 ✓
6:  0110 & 0101 = 0100 ✗
8:  1000 & 0111 = 0000 ✓

7. 统计1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 方法1：Brian Kernighan算法（推荐）
int countOnes(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // 清除最右边的1
        count++;
    }
    return count;
}

// 方法2：逐位检查
int countOnes2(int n) {
    int count = 0;
    while (n) {
        count += (n & 1);
        n >>= 1;
    }
    return count;
}

// 方法3：C++内置函数
int countOnes3(int n) {
    return __builtin_popcount(n);
}

效率对比：

  • 方法1：O(k)，k为1的个数
  • 方法2：O(32)
  • 方法3：编译器优化，最快

经典LeetCode问题

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

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例：

1
2
3
4
5
输入：[2,2,1]
输出：1

输入：[4,1,2,1,2]
输出：4

解法：异或

1
2
3
4
5
6
7
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

原理：

1
2
3
4
5
6
7
8
9
a ^ a = 0
a ^ 0 = a
交换律和结合律

[4,1,2,1,2]
= 4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

时间复杂度：O(n)
空间复杂度：O(1)

2. 位1的个数（LeetCode 191）

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数。

示例：

1
2
输入：11 (0000...1011)
输出：3

解法：Brian Kernighan算法

1
2
3
4
5
6
7
8
int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // 清除最右边的1
        count++;
    }
    return count;
}

过程演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = 11 (1011)

第1次：n = 1011
      n-1 = 1010
      n & (n-1) = 1010, count=1

第2次：n = 1010
      n-1 = 1001
      n & (n-1) = 1000, count=2

第3次：n = 1000
      n-1 = 0111
      n & (n-1) = 0000, count=3

结束，返回3

3. 2的幂（LeetCode 231）

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

1
2
3
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

原理：

1
2
3
4
5
6
7
8
2的幂只有一个1：
2:   0010
4:   0100
8:   1000

非2的幂有多个1：
3:   0011
6:   0110

4. 颠倒二进制位（LeetCode 190）

颠倒给定的 32 位无符号整数的二进制位。

示例：

1
2
输入：43261596 (00000010100101000001111010011100)
输出：964176192 (00111001011110000010100101000000)

解法：逐位翻转

1
2
3
4
5
6
7
8
uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; ++i) {
        result = (result << 1) | (n & 1);  // 取n最低位，加到result末尾
        n >>= 1;                            // n右移
    }
    return result;
}

过程演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = 1011 (只看4位)

i=0: result = 0, n=1011
     result = (0 << 1) | 1 = 1
     n = 0101

i=1: result = 1, n=0101
     result = (1 << 1) | 1 = 11
     n = 0010

i=2: result = 11, n=0010
     result = (11 << 1) | 0 = 110
     n = 0001

i=3: result = 110, n=0001
     result = (110 << 1) | 1 = 1101
     n = 0000

结果：1101（原数1011的翻转）

5. 只出现一次的数字III（LeetCode 260）

给定一个整数数组，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例：

1
2
输入：[1,2,1,3,2,5]
输出：[3,5]

解法：分组异或

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> singleNumber(vector<int>& nums) {
    // 步骤1：全部异或，得到两个单独数字的异或结果
    int xorResult = 0;
    for (int num : nums) {
        xorResult ^= num;
    }
    
    // 步骤2：找到xorResult中任意一个为1的位
    // 这一位在两个数字中不同
    int rightmostBit = xorResult & (-xorResult);
    
    // 步骤3：根据这一位分组
    int num1 = 0, num2 = 0;
    for (int num : nums) {
        if (num & rightmostBit) {
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }
    
    return {num1, num2};
}

原理图解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
[1,2,1,3,2,5]

步骤1：全部异或
1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = 3 ^ 5 = 0011 ^ 0101 = 0110

步骤2：找最右边的1
0110 & (-0110) = 0010

步骤3：按第2位分组
第2位为0：1(0001), 1(0001), 3(0011), 5(0101)
第2位为1：2(0010), 2(0010)

组1异或：1 ^ 1 ^ 3 ^ 5 = 3 ^ 5 = 6... 错了？
应该是：
第2位为1：2(0010), 2(0010)
第2位为0：1(0001), 1(0001), 3(0011), 5(0101)

重新分析：
rightmostBit = 0010

第2位为1：2, 2 → 异或 = 0
第2位为0：1, 1, 3, 5 → 异或 = 3 ^ 5

不对，让我重新理解：
按照这一位把所有数分成两组，每组内成对的会消掉，剩下各自的单独数字

6. 比特位计数（LeetCode 338）

给定一个非负整数 num，对于范围 [0, num] 中的每个数字，计算其二进制表达式中 1 的个数。

示例：

1
2
3
4
5
6
7
8
9
10
输入：5
输出：[0,1,1,2,1,2]

解释：
0: 0000 → 0个1
1: 0001 → 1个1
2: 0010 → 1个1
3: 0011 → 2个1
4: 0100 → 1个1
5: 0101 → 2个1

解法1：动态规划 + 最低位

1
2
3
4
5
6
7
vector<int> countBits(int n) {
    vector<int> result(n + 1);
    for (int i = 1; i <= n; ++i) {
        result[i] = result[i >> 1] + (i & 1);
    }
    return result;
}

原理：

1
2
3
4
5
6
7
8
i的1的个数 = (i/2)的1的个数 + i的最低位

例如：
6 (110) = 3 (11) 向右移一位 + 0 (最低位)
        = 2个1 + 0 = 2

7 (111) = 3 (11) 向右移一位 + 1 (最低位)
        = 2个1 + 1 = 3

解法2：动态规划 + 清除最低位

1
2
3
4
5
6
7
vector<int> countBits(int n) {
    vector<int> result(n + 1);
    for (int i = 1; i <= n; ++i) {
        result[i] = result[i & (i - 1)] + 1;
    }
    return result;
}

原理：

1
2
3
4
i的1的个数 = (i清除最低位后)的1的个数 + 1

6 (110) = 4 (100) 清除最低位 + 1
        = 1个1 + 1 = 2

时间复杂度：O(n)
空间复杂度：O(n)

7. 汉明距离（LeetCode 461）

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

示例：

1
2
3
4
5
6
7
输入：x = 1, y = 4
输出：2

解释：
1: 0001
4: 0100
不同位：2个

解法：异或 + 计数

1
2
3
4
5
6
7
8
9
10
11
int hammingDistance(int x, int y) {
    int xorResult = x ^ y;  // 不同的位为1
    int count = 0;
    
    while (xorResult) {
        xorResult &= (xorResult - 1);  // 清除最右边的1
        count++;
    }
    
    return count;
}

高级技巧

1. 子集生成（状态压缩）

用位运算生成集合的所有子集：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;
    
    // 遍历0到2^n-1的所有数字
    for (int mask = 0; mask < (1 << n); ++mask) {
        vector<int> subset;
        for (int i = 0; i < n; ++i) {
            // 检查第i位是否为1
            if (mask & (1 << i)) {
                subset.push_back(nums[i]);
            }
        }
        result.push_back(subset);
    }
    
    return result;
}

原理：

1
2
3
4
5
6
7
8
9
10
11
nums = [1,2,3]
用3位二进制表示：

000: []
001: [1]
010: [2]
011: [1,2]
100: [3]
101: [1,3]
110: [2,3]
111: [1,2,3]

2. N皇后位运算优化

使用位运算优化N皇后问题的状态表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solveNQueens(int row, int cols, int diag1, int diag2, int n) {
    if (row == n) {
        // 找到一个解
        return;
    }
    
    // 可放置的位置：未被占用的列和对角线
    int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
    
    while (available) {
        int position = available & (-available);  // 取最右边的1
        
        // 放置皇后
        solveNQueens(row + 1, 
                     cols | position,
                     (diag1 | position) << 1,
                     (diag2 | position) >> 1,
                     n);
        
        // 移除这个位置
        available &= (available - 1);
    }
}

优势：

  • 用整数表示状态，节省空间
  • 位运算速度快

位运算口诀

常用技巧记忆

1
2
3
4
5
6
7
1. 判断奇偶：n & 1
2. 乘以2：n << 1
3. 除以2：n >> 1
4. 交换不用临时变量：a ^= b; b ^= a; a ^= b;
5. 清除最右边的1：n & (n-1)
6. 获取最右边的1：n & (-n)
7. 判断2的幂：n & (n-1) == 0

异或的神奇性质

1
2
3
自己异或自己等于0：a ^ a = 0
任何数异或0等于自己：a ^ 0 = a
满足交换律和结合律

总结

核心要点

  1. 异或是王者：大多数位运算题目的核心
  2. n & (n-1)：清除最右边的1，超级实用
  3. 状态压缩：用位表示集合状态
  4. 效率优势：位运算比普通运算快

常用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 1. 统计1的个数
int countOnes(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

// 2. 判断2的幂
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// 3. 获取/设置/清除第k位
int getBit(int n, int k) { return (n >> k) & 1; }
int setBit(int n, int k) { return n | (1 << k); }
int clearBit(int n, int k) { return n & ~(1 << k); }

// 4. 异或找单独数字
int findSingle(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

推荐题目

入门级：

进阶级：

高级：

推荐阅读：