位运算的巧妙应用

一、基本位运算

运算符	说明	示例
&	与	1 & 1 = 1
|	或	1 | 0 = 1
^	异或	1 ^ 1 = 0
~	非	~1 = 0
<<	左移	1 << 2 = 4
>>	右移	4 >> 1 = 2

二、常用技巧

2.1 判断奇偶

// 代替 n % 2 == 0
boolean isEven = (n & 1) == 0;

2.2 交换变量

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

2.3 获取最低位1

int lowbit = x & (-x);
// 例: x = 10100, -x = 01100, lowbit = 00100 = 4

2.4 清除最低位1

x = x & (x - 1);
// 例: x = 10100, x-1 = 10011, x & (x-1) = 10000

2.5 判断是否为2的幂

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

三、经典问题

3.1 只出现一次的数

// 其他数出现两次，只有一个出现一次
public int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) res ^= num;
    return res;
}

3.2 只出现一次的数 II

// 其他数出现三次
public int singleNumberII(int[] nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    return ones;
}

3.3 统计1的个数

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

3.4 判断字符是否唯一

public boolean isUnique(String s) {
    int mask = 0;
    for (char c : s.toCharArray()) {
        int bit = 1 << (c - 'a');
        if ((mask & bit) != 0) return false;
        mask |= bit;
    }
    return true;
}

四、状态压缩DP

用二进制表示状态集合：

// n ≤ 20 时，可用int表示状态
int state = 0;  // 二进制第i位表示第i个元素是否选中
state |= (1 << i);  // 选中第i个
if ((state & (1 << i)) != 0)  // 判断是否选中

五、总结

位运算直接操作二进制位，效率极高。掌握常见技巧，可以在判断、统计、状态表示等场景中写出简洁高效的代码。