LeetCode338. 比特位计数

题目连接

https://leetcode-cn.com/problems/counting-bits/

解题思路

这道题需要计算从 0 到 num 的每个数的二进制表示中的 1 的数目。最直观的方法是对每个数直接计算二进制表示中的 1 的数目，时间复杂度较高。也可以使用动态规划的方法，时间复杂度较低。

为了表述简洁，下文用「一比特数」表示二进制表示中的 1 的数目。

方法一：暴力

暴力，时间复杂度O(n*sizeof(integer)) 注意，虽然是暴力，但是仍可以进行优化。 按位与运算（&）的一个性质是： 对于任意整数 x，令 x=x&(x−1)，该运算将 x 的二进制表示的最后一个 1变成 0。 因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」

方法二：dp

• 最高有效位 方法一需要对每个数遍历其二进制表示的每一位。可以换一个思路，当计算 i 的「一比特数」时，如果存在 0≤j1]+(x&1)。

  遍历从 1 到 num 的每个正整数 i，计算 bits 的值。最终得到的数组 bits 即为答案。

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

• 最低设置位

  定义正整数 xx 的「最低设置位」为 xx 的二进制表示中的最低的 11 所在位。例如，1010 的二进制表示是 1010 ，其最低设置位为 2，对应的二进制表示是 10 。

  令 y=x&(x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然 0≤y