338. 比特位计数（高频题）

338. 比特位计数

• 解题思路
• 代码

解题思路

其实这就是一个数学题，找到规律了就很简单

• 一个数比如a，如果是偶数，那么a比特位1的个数和(a/2)比特位1的个数是一样的，因为一个数是偶数那么他的二进制比他的一半的二进制只是多了一个0而已。
  

• 如果是奇数就不一样了，他会比除以2的结果多了一个1（比如9的二进制比4的二进制多一个1，19的二进制比9的二进制多一个1，等等）。
  

代码

public class Solution {
    public int[] countBits(int num) {
        int[] ans = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            if (i % 2 == 0) {
                ans[i] = ans[i / 2];
            } else {
                ans[i] = ans[i / 2] + 1;
            }
        }
        return ans;
    }
}