跳到主要内容

位运算

问题​

Java 中位运算相关的常见算法题有哪些？

答案​

位运算基础​

运算符含义示例
&与5 & 3 = 1（101 & 011 = 001）
|或5 | 3 = 7（101 | 011 = 111）
^异或5 ^ 3 = 6（101 ^ 011 = 110）
~取反~5 = -6
<<左移1 << 3 = 8
>>右移8 >> 2 = 2
常用技巧
  • n & (n - 1) → 消除最低位的 1
  • n & (-n) → 获取最低位的 1
  • a ^ a = 0，a ^ 0 = a → 异或自消

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

异或：相同数抵消
public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) result ^= num;
    return result;  // 所有成对的数异或为 0，剩下的就是单独的
}

位 1 的个数（LeetCode 191）​

Brian Kernighan 算法
public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);  // 每次消除最低位的 1
        count++;
    }
    return count;
}

2 的幂（LeetCode 231）​

public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;  // 2 的幂只有一个 1
}

两整数之和（不用 +/-）（LeetCode 371）​

位运算模拟加法
public int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;  // 进位
        a = a ^ b;                  // 无进位加法
        b = carry;
    }
    return a;
}

权限控制（实际应用）​

位掩码权限控制
public class Permission {
    static final int READ    = 1;      // 0001
    static final int WRITE   = 1 << 1; // 0010
    static final int EXECUTE = 1 << 2; // 0100
    static final int DELETE  = 1 << 3; // 1000
    
    int permission = 0;
    
    void grant(int p) { permission |= p; }    // 授予
    void revoke(int p) { permission &= ~p; }  // 撤销
    boolean has(int p) { return (permission & p) == p; }  // 检查
}

常见面试问题​

Q1: 为什么 HashMap 容量是 2 的幂？​

答案：

因为 hash & (capacity - 1) 等价于 hash % capacity，位运算比取模快。2 的幂减 1 后所有低位都是 1，能均匀分布。详见 HashMap 源码解析。

Q2: 如何不用临时变量交换两个数？​

答案：

a ^= b;
b ^= a;  // b = a ^ b ^ b = a
a ^= b;  // a = a ^ a ^ b = b（原始 b）

Q3: 位运算常见的面试考点？​

答案：

  • 异或性质（自消、交换律）
  • n & (n-1) 消除最低位 1
  • 位掩码做权限/状态管理
  • 左移右移代替乘除 2

相关链接​