本文共 1857 字，大约阅读时间需要 6 分钟。

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2

输入：n = 5

1.自己的想法就是计算出每个数字的二进制含有的1的个数，但是这样时间效率很低。

class Solution {    public int[] countBits(int n) {        int[] counts = new int[n + 1];        for (int i = 0;i <= n;i++) {            counts[i] = countBit(i);        }        return counts;    }    public int countBit(int number) {        int count = 0;        while (number >= 2) {            int a = number % 2;//余数            if (a == 1) {                count++;            }            number = number / 2;        }        if (number == 1) {            count++;        }        return count;    }}

2.题解：

        Brian Kernighan 算法。原理是：对于任意整数 x，令x=x & (x−1)，该运算将x的二进制表示

      的最后一个1变成0。因此，对x重复该操作，直到x变成0，则操作次数即为x的「一比特数」。

class Solution {    public int[] countBits(int n) {        int[] bits = new int[n + 1];        for (int i = 0; i <= n; i++) {            bits[i] = countOnes(i);        }        return bits;    }    public int countOnes(int x) {        int ones = 0;        while (x > 0) {            x &= (x - 1);            ones++;        }        return ones;    }}

        动态规划----最高有效位：i & (i - 1)可以去掉i最右边的一个1（如果有），因此 i & (i - 1）是比

      i 小的，而且i & (i - 1)的1的个数已经在前面算过了，所以i的1的个数就是 i & (i - 1)的1的个数加

     上1。

public int[] countBits(int num) {    int[] res = new int[num + 1];    for(int i = 1;i<= num;i++){  //注意要从1开始，0不满足        res[i] = res[i & (i - 1)] + 1;    }    return res;}

        动态规划----最低有效位：i >> 1会把最低位去掉，因此i >> 1 也是比i小的，同样也是在前面的

      数组里算过。当 i 的最低位是0，则 i 中1的个数和i >> 1中1的个数相同；当i的最低位是1，i 中

      1的个数是 i >> 1中1的个数再加1。

public int[] countBits(int num) {    int[] res = new int[num + 1];    for(int i = 0;i<= num;i++){        res[i] = res[i >> 1] + (i & 1);  //注意i&1需要加括号    }    return res;}

        这三种动态规划解法来自评论@horanal。积累一下

题源：

转载地址：https://blog.csdn.net/xxyneymar/article/details/122057767 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！