338. 比特位计数 (opens new window)

1.暴力

分析：对于每一个索引下标，通过除法和取余运算统计当前元素比特位上1的个数

class Solution {
    public int[] countBits(int n) {
        int[] res=new int[n+1];
        for(int i=1;i<=n;i++){
            int sum=0,temp=i;
            while(temp!=0){
                if(temp%2==1) sum++;
                temp=temp>>1;
            }
            res[i]=sum; 
        }
        return res;
    }
}

2.奇偶判断

本质是考虑当前元素比特位上的最低位，转化为已知的子问题结果。根据当前元素的奇偶性进行判断：

• 当前元素如果为奇数，那么它的比特位计数一定等于前一个偶数的比特位计数加一，因为他们除了末位不相同以外，其它高位全都一致。
• 如果当前元素为偶数，那么它的比特位计数，一定等于该元素除以2的结果的比特位计数。因为偶数的最低位一定为0，因此右移一位后(相当于除以2)得到结果的比特位计数不会有变化。

3.动态规划

状态转移方程bits[x]=bits[z]+1，其中z=x-不大于x的最大2的整数次幂。具体来说：如果要计算7的比特位数，它的比特位数等于7-4=3的比特位数加一。转化成二进制数来看，111的比特位数等于减去最大2的整数次幂11的比特位数加上1。

而对于一个数x，如何求出它的最大二的整数次幂。

如果一个数是二的整数次幂，那么只有一个最高位的1，其它位均为0。拿他减去1后，所有比最高位小的比特位都为1。 举例子：8的比特位1000，减1后0111

public int highBit(int x){
	return x&(x-1)==0;
}