题目来源

338. 比特位计数

思路

方法一

暴力解法

class Solution {
    public int[] countBits(int num) {
        int[] ans = new int[num+1];
        for(int i = 0;i<=num;i++){
            ans[i] = count(i);
        }
        return ans;
    }

    public int count(int n){
        int ans = 0;
        int a = n;
        int b = 0;
        while(a != 0){	// 辗转相除法
            b = a%2;	// 求余数
            a /= 2;		// 更新被除数
            if(b == 1){
                ans++;
            }
        }
        return ans;
    }
}

用位运算减少时间

public int count(int n){
    int one = 0;
    while(n > 0){
        n = n&(n-1);	// 改变二进制中最后一位1为0，并更新
        one++;
    }
    return one;
}

方法二 简单的动态规划

在二进制中，

对于奇数来说，其中的\(1\)的个数一定比它前面一个的偶数的个数多\(1\)，因为多的就是最低为的\(1\)。

举例：
         0 = 0       1 = 1
         2 = 10      3 = 11

对于偶数来说，其中的\(1\)的个数一定和它除以\(2\)以后的数一样多。因为最低位位\(0\)，除以\(2\)后，相当于右移一位，也就是把\(0\)去掉，\(1\)的个数不变。

举例：
          2 = 10       4 = 100       8 = 1000
          3 = 11       6 = 110       12 = 1100

  • 如果 \(x\) 是偶数，则ans[i] = ans[i>>1]

  • 如果\(x\)是奇数，则ans[i] = ans[i>>1]+1

以上两种情况可以合并成为：ans[i] = ans[i>>1] + (i&1)

i>>1 表示右移一位，i&1 表示求\(i\)除以\(2\)的余数

class Solution {
    public int[] countBits(int num) {
        int[] ans = new int[num+1];
        ans[0] = 0;
        for(int i = 1;i<=num;i++){	
            if((i & 1) == 0){		// 偶数
                ans[i] = ans[i>>1];
            }else{				// 奇数
                ans[i] = ans[i-1]+1;
            }
        }
        return ans;
    }
}

位运算优先级比较低，所以要加括号 \((i\&1)\)

方法三 动态规划——最低设置位

最低设置为定义为，x的二进制表示中的最低的1所在的位置。

令\(y = x \& (x-1)\)，则\(y\)位将\(x\)的最低设置位从\(1\)变成\(0\)之后的数，显然\(0\le y \le x\)，\(ans[x] = ans[y]+1\)，因此对任意正整数\(x\)，都有\(ans[x] = ans[x\&(x-1)]+1\)

class Solution {
    public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    }
}

参考来源

  1. 官方题解
  2. duadua