Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

大意为在给定的一个数字，求对于每一个小于这个数字的非负整数的二进制形式中有多少 1。

思路

在二进制运算中有一个基本但是神奇的运算 & ，与运算的原则是同为 1 相与则为 1，一旦有 0 相与则为 0，

因此在位运算中有一个神奇的规律，当一个正整数数 x 与 (x-1) 相与时，x 二进制中的最右端的 1 则会消去

如：

010010101
&
010010100
=
010010100


010100100
&
010100011
=
010100000

由此规律可知，当一个数 x 与 (x-1) 相与多次，直到结果为 0，则相与次数则为 x 二进制中 1 的个数

代码

public int[] countBits(int num) {
    int[] ret = new int[num + 1];
    for (int i = 0; i <= num; i++) {
    	int tmp = i;
    	while (tmp > 0) {
            tmp = tmp & (tmp - 1);
            ret[i]++;
    	}
    }
    return ret;
}