面试中经常会用到位操作，这里把Cracking the Coding Interview里讲到的常用的位操作整理一下，加上一些其他的常用的位操作

Get Bit

1
2
3
boolean getBit(int num, int i) {
  return ((num & (1 << i)) != 0);
}

Set Bit

1
2
3
int setBit(int num, int i) {
  return num | (1 << i);
}

Clear Bit

1
2
3
4
int clearBit(int num, int i) {
  int mask = ~(1 << i);
  return num & mask;
}

Update Bit

1
2
3
4
5
int updateBit(int num, int i, boolean bitIs1) {
  int value = bitIs1 ? 1 : 0;
  int mask = ~(1 << i);
  return (num && mask) | (value << i);
}

n & (n - 1) 常见用法

  1. 求一个数的二进制中1的个数
    191. Number of 1 Bits

    1
    2
    3
    4
    5
    6
    7
    8
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }

  2. 判断一个数是否是2的指数
    231. Power of Two

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

  3. 计算n!的质因数2的个数

异或xor的妙用

未完待续