算法：位运算

位运算题型与Java算法技巧

一、位运算基础

位运算特点

• XOR 特性：

  • a ^ a = 0
  • a ^ 0 = a
  • a ^ b ^ a = b

• 检查奇偶性： (n & 1) == 0 偶数， (n & 1) == 1 奇数

• 快速乘除 2 的幂：

  • n << k → n * (2^k)
  • n >> k → n / (2^k)

• 清零/取低位：

  • n & (n-1) → 清掉最低位的 1
  • n & -n → 取出最低位的 1

二、题型分类与技巧

1. 判断奇偶

• 示例题: LeetCode 231. 2 的幂

boolean isOdd(int n) {
    return (n & 1) == 1;
}

2. 交换两个数

a ^= b;
b ^= a;
a ^= b;

3. 数组中唯一出现的数

• 示例题: LeetCode 136. Single Number

int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) res ^= num;
    return res;
}

4. 位计数 / 汉明重量

• 示例题: LeetCode 191. Number of 1 Bits

int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

5. 判断是否为 2 的幂

• 示例题: LeetCode 231. 2 的幂

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

6. 子集 / 状态压缩 DP

• 示例题: LeetCode 78. Subsets

int n = 3;
for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            System.out.print(i + " ");
        }
    }
    System.out.println();
}

7. 快速乘除法

int mul = n << 3; // n * 8
int div = n >> 2; // n / 4

8. 找出二进制中不同的位

• 示例题: LeetCode 260. Single Number III

int diffBit = a ^ b;
int lowestDiff = diffBit & -diffBit;

三、位运算常用模板

1. XOR 找单数

int res = 0;
for (int num : nums) res ^= num;
return res;

2. 清零最低位 1

while (n != 0) {
    n &= (n-1);
}

3. 子集遍历

for (int mask = 0; mask < (1<<n); mask++) {
    // 遍历 mask 的每一位
}

4. 判断 2 的幂

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

5. 交换两个数

a ^= b; b ^= a; a ^= b;