Bit Manipulation，对于 '1' 位的操作

• 对付 unsigned int 要把判断条件改为 xx != 0 而不是 xx > 0

• (n & -n) 是找 n 的 binary 里最右面的 1 所代表的数

• n - (n & -n) 效果为减去 n 的二进制表示中最右边为 1 的 bit

• n + (n & -n) 就是直接在最低位的 1 上做进位加法。

Number of 1 Bits

这题因为是 un-signed int，最高位 = 1 的情况稍微特殊点，把条件改成 != 0 就行了。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for(int i = 0; i < 32; i++){
            if((n & (1 << i)) != 0) count ++;
        }
        return count;
    }
}

另一种做法是这样，会每次移除最末尾的 siginificant digit，直到 n = 0 为止。

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

Reverse Bits

注意 shift rst 的顺序，先 shift，再赋值。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int rst = 0;
        for(int i = 0; i < 32; i++){
            rst = rst << 1;
            if(((n & (1 << i)) != 0)) rst += 1;
        }
        return rst;
    }
}

Counting Bits

此题重点和难点在于：Do it like a Boss.

• 12 :..............0000001100

• -12 :............11111110100

• 12 & -12:.....0000000100

n - (n & -n) 效果为减去 n 的二进制表示中最右边为 1 的 bit

由于结果肯定比 n 小，bit 数又一定只比 n 多一个，就可以迭代求解了~

Fenwick Tree 万岁~

public class Solution {
    public int[] countBits(int num) {
        int[] rst = new int[num + 1];

        for(int i = 1; i <= num; i++){
            // previous index = Remove most significant digit
            // then add one as current bit.
            rst[i] = rst[i - (i & -i)] + 1;
        }

        return rst;
    }
}

另一种思路是基于这个公式：

• f[i] = f[i / 2] + i % 2.

public int[] countBits(int num) {
    int[] f = new int[num + 1];
    for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1);
    return f;
}