[数据结构与算法]前n个数中二进制中1的个数

剑指Offer II 003

给定一个非负整数?n?，请计算?0?到?n?之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

图解

//思路一 此处只写 计算二进制中一的个数的函数
public int count(int n){
    int count = 0;
    while(n != 0){
        n &= (n-1);
        count++;
    }
    return count;
}
//思路二
可以自己尝试以下，与思路三大致相同

?

//思路三
class Solution {
    public int[] countBits(int n) {
        int[] count = new int[n+1];
        int high = 0;
        for(int i=1;i<=n;i++){
            //等于0，表示这个i 为 “y”
            if((i&(i-1))==0){
                high = i;
            }
            count[i] = count[i-high]+1;
        }
        return count;
    }
}
//思路四
class Solution {
    public int[] countBits(int n) {
        int[] count = new int[n+1];
        for(int i=1;i<=n;i++){
            count[i] = count[i>>1]+(i&1);
        }
        return count;
    }
}

?