【剑指Offer2】003-前n个数字二进制中1的个数

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

动态规划解法——最高有效位

思路

用 bits[i] 来表示 i 的二进制中 1 的个数。

对于一个正整数 x，如果它是 2 的整数次幂，那么它的二进制只有第一位为 1，其余位均为 0。

判断一个正整数是否为 2 的整数次幂

对于正整数 i，如果能找到第一个比它小的并且是 2 的整数次幂的值 y，则 i 的二进制 1 的数量 bits[i] 等于 y 的二进制 1 的数量bits[y] 加上 i 除去最高位的 i - y 的二进制数量 bits[i - y] 。

来自评论区的“泛舟当歌”：比如 66，他和 64 一样的最高位，那么 66 的二进制个数就等于去掉最高位以后，剩下二进制位的数加上最高位的那个 1，而 66 去掉最高位就是 66-64=2，那么 2 的二进制个数是 1 个，66 则是 1+1=2 个。

复杂度

• 时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。

• 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。

代码

var countBits = function (n) {
  const bits = new Array(n + 1).fill(0);
  let hightBit = 0;
  for (let i = 1; i <= n; i++) {
    if ((i & (i - 1)) === 0) {
      hightBit = i;
    }
    bits[i] = bits[i - hightBit] + 1;
  }
  return bits;
};
let result = countBits(66);
console.log(result);