面试中经常会用到位操作,这里把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的妙用

未完待续