338. 比特位计数

题目

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

题解

直接计算

/**
 * @param {number} num
 * @return {number[]}
 */
var countBits = function(num) {
  let res = [];
  let i = 0;
  while (i <= num) {
    res.push(count(i++));
  }
  return res;
};
// 利用十进制转换二进制的方法：除2取余为1则该位为1
function count(n) {
  let c = 0;
  while (n) {
    if (n % 2) c++;
    n = n >> 1;
  }
  return c;
}

动态规划——最低设置位

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

令 y=x&(x−1)(该运算将 x 的二进制表示的最后一个 1 变成 0)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然 0≤y<x，bits[x]=bits[y]+1。因此对任意正整数 x，都有 bits[x]=bits[x&(x−1)]+1。

/**
 * @param {number} num
 * @return {number[]}
 */
var countBits = function(num) {
  const bits = new Array(num + 1).fill(0);
  for (let i = 1; i <= num; i++) {
    bits[i] = bits[i & (i - 1)] + 1;
  }
  return bits;
};