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$ 的二进制位数相等。
1 | class Solution: |
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$;
1 | class Solution: |
五、补充
判断一个二进制数是否最高位为 $1$ 且其余位为0:$x\&(x-1)==0$ ;
$x=x\&(x-1)$,该运算将 $x$ 的二进制数最后一个 $1$ 变为 $0$。