位运算

位1的个数

// you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        if (n == 0) {
            return 0;
        }
        int count = 0;
        do {
            n = n & (n - 1);
            count ++;
        } while (n != 0);
        return count;
    }

2的幂

// &运算的特性
public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        return (n & (n - 1)) == 0;
    }

比特位计数

// 第一种方法，类似于位1的个数的解法，将[0,num]中的每个数求解1的个数，然后放入数组中，时间复杂度为O(n*sizeOf(num))，较慢
// 第二种方法，开辟一个int[num+1]的数组，第i个数字的1的个数，一定是i&i-1位的1个数+1，有点类似于位1的个数中的循环，因此可得出公式 int[i] = int[i&i-1] + 1
// 代码如下
public int[] countBits(int num) {
        int[] resArr = new int[num + 1];
        for (int i = 1; i <= num; i ++) {
            resArr[i] = resArr[i & (i - 1)] + 1;
        }
        return resArr;
    }