跳到主要内容

位运算

位运算（Bit Manipulation）是计算机底层最快速的操作之一，在某些算法中能够提供 O(1) 的巧妙解法。

常用算子​

算子名称功能
&按位与均为 1 则为 1
``按位或
^异或相同为 0，不同为 1
~取反01 互换
<<左移相当于乘以 2
>>右移相当于除以 2

经典算法技巧​

1. 异或运算的特殊性质​

  • x ^ 0 = x
  • x ^ x = 0
  • x ^ y = y ^ x (交换律)

实例：只出现一次的数字 (LeetCode 136) 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。

  • 解法：对所有元素进行异或。成对的元素异或为 0，最后剩下的就是那一个唯一的数字。

2. 位运算技巧总结​

// 判断奇偶
(n & 1) == 0; // 偶数
(n & 1) == 1; // 奇数

// 二进制中 1 的个数 (Hamming Weight)
int count = 0;
while (n != 0) {
    n &= (n - 1); // 清除最低位的 1
    count++;
}

// 判断 n 是否为 2 的幂
(n > 0) && ((n & (n - 1)) == 0);

// 获取最低位的 1 (lowbit)
int lowbit = n & (-n);

3. 位运算的应用场景​

  • 状态压缩 (如 N 皇后、TSP、子集枚枚)。
  • 子集生成 (如使用一个整数的 1 代表某位被选中)。

练习​

  1. LeetCode 136/137/260：只出现一次的数字系列
  2. LeetCode 191：位 1 的个数
  3. LeetCode 231：2 的幂
  4. LeetCode 338：比特位计数 (位运算 + DP)
  5. LeetCode 52：N 皇后 II (位运算加速极其高效)