338. 比特位计数

1. 直接计算

• 按位与运算（&）的一个性质是：对于任意整数 x，令 x=x &(x-1)，该运算可以将 x 的二进制表示的最后一个 1 变成 0。

• 对 x 重复该操作，直到 x 变成 0，可以统计出x的二进制表示中有多少1，原理分析如下：

  • 设x的二进制表示为[x0, x1, ..., xn]，其中数值为1的最低位为m。
  • (x-1)相当于[x0,...,xm+1]保持不变，[xm,...,xn]按位取反。
  • x&(x-1)相当于[x0,...,xm+1]保持不变，[xm,...,xn]全部变为0。
  • 以上三个步骤循环进行，只到所有数位变为0，循环次数即为1的个数。

class Solution:
    def countBits(self, num: int) -> List[int]:
       
        def countOnes(x):
            ones = 0
            while x > 0:
                x &= (x-1)
                ones += 1
            return ones 

        results = [countOnes(i) for i in range(num+1)]
        return results

2. 动态规划-最高有效位

• 对于正整数 x，如果可以知道最大的正整数 y，使得 y≤x 且 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，此时称 y 为 x 的最高有效位，并且有bits[x] = bits(x-y) + bits(y) = bits(x-y) + 1
• 如果正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，因此 y &(y-1)=0。由此可见，正整数 y 是 2 的整数次幂，当且仅当 y &(y-1)=0。
• 算法：遍历从 1到 num 的每个正整数 i，进行如下操作
  • 如果 i &(i-1)=0，则令bits[i]=1且highbit=i，更新当前的最高有效位。
  • 如果 i &(i-1)!=0，bits[i]=bits[i-highbit]+h[highbit]=bits[i-highbit]+1

class Solution:
    def countBits(self, num: int) -> List[int]:
        results = [0]
        highbit = 0
        for i in range(1, num+1):
            if i&(i-1)==0:
                results.append(1)
                highbit = i
            else:
                results.append(results[i - highbit] + 1)       
        return results