LeetCode338. 比特位计数 i=(i-1)&1 详解
LeetCode338. 比特位计数 i=(i-1)&1 详解
题目描述：
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
i= (i-1)&i i>1
功能： 在i的二进制表示中，将右数第一个1置0。 i = 6 10 = 11 0 2 i=6_{10}=110_2 i=610=1102, ( i − 1 ) (i-1) (i−1)& i = 10 0 2 i=100_2 i=1002
实现原理:
建议将i=6，用二进制表示，将(i-1)&i手动计算一边
- (i-1) 会将i右数第一1置0，这个位置记为P，而P右侧的0将变成1。 11 0 2 − 1 = 10 1 2 110_2-1=101_2 1102−1=1012，最低位的1是P位上借来的。
- (i-1)&i i>0 比P高的bit位，即P的左侧，(i-1)与i是相同的 (i-1)的P位0 比P低的bit位，(i-1)全为1 综上三点：(i-1)&i等于将 i的第一个1置0
DP
dp[i]: 表示i的二进制表示中1的个数。于是有dp[i]=dp[(i-1)&i]+1
class Solution {
public int[] countBits(int num) {
int[] dp = new int[num+1];
for(int i=1;i<=num;i++){
dp[i] = dp[(i-1)&i]+1;
}
return dp;
}
}
后记
(i-1)&i常规操作啦，感受下 中 sub=(sub-1)&mask的恐惧吧
上一篇：
通过多线程提高代码的执行效率例子
下一篇：
高效能人士的七个习惯