算法自由之路

前n个数字二进制中1的个数

题目

剑指 Offer II 003.前n个数字二进制中1的个数

思路

Brian Kernighan 算法的原理是：对于任意整数 xx，令 x = x & (x-1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」

代码

1.方法一：Brian Kernighan 算法

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const res = new Array(n + 1).fill(0);
  const countOnes = (a) => {
    let count = 0;
    while (a > 0) {
      a &= a - 1;
      count++;
    }
    return count;
  };

  for (let i = 0; i <= n; i++) {
    res[i] = countOnes(i);
  }
  
  return res;
};