LeetCode338:比特位计数

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

4.1 动态规划——最高有效位

记 $dp[i]$ 表示索引 $i$ 所对应二进制数的 $「1比特数」$。

• 如果最高位为 $1$ 且其余位均为 $0$，即 $i \& (i-1)=0$，有 $dp[i]=1$ 。
• $i$ 比 $i-highBit$ 的 $「1比特数」$ 多 $1$ ，即 $dp[i] = dp[i-highBit]+1$

其中，$highBit$ 是二进制最高位为 $1$ 且其余位为 $0$ 的数，$i$ 和 $highBit$ 的二进制位数相等。

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp, h = [0 for _ in range(n+1)], 2
        for i in range(1, n+1):
            if i & (i-1) == 0:
                h = i
                dp[i] = 1
            dp[i] = dp[i - h] + 1
        return dp

4.2 动态规划——最低有效位

对于正整数 $x$ ，将其二进制表示右移一位，得到的数是 $\lfloor \frac{x}{2} \rfloor$，如果 $dp[\lfloor \frac{x}{2} \rfloor]$ 的值已知，则可以得到 $dp[x]$ 的值：

• 如果 $x$ 是偶数， 则 $dp[x]=dp[\lfloor \frac{x}{2} \rfloor]$；
• 如果 $x$ 是奇数，则 $dp[x]=dp[\lfloor \frac{x}{2} \rfloor]+1$；

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n+1)
        for i in range(1, n + 1):
            dp[i] = (dp[i >> 1] + (i & 1))
        return dp

五、补充

• 判断一个二进制数是否最高位为 $1$ 且其余位为0：$x\&(x-1)==0$ ；

• $x=x\&(x-1)$，该运算将 $x$ 的二进制数最后一个 $1$ 变为 $0$。