我一直弄错这个问题。使用JavaScript计数位

Question

这是一个问题。 给定一个整数n，返回一个长度为n + 1的数组and and and n + 1，以便对于每个i（0＆lt; = i＆lt; = n），ans [i]是i的二进制表示中的1个数字。

”以下。 如果输入为2，则预期输出应为[0,1,1]，但我一直得到[0,2,2]。这是为什么？？？

var countBits = function(n) {
    //n=3. [0,1,2,3]
    var arr=[0];
     for (var i=1; i<=n; i++){
         var sum = 0;
         var value = i;
         while(value != 0){
             sum += value%2;
             value /= 2;
         }
         arr.push(sum);
     }
    return arr;
};

console.log(countBits(3));

Answer 1

您正在做太多工作。

假设b是与i中第一个位相对应的2的最大功率。显然，i与i -b相比，其二进制表示中的一个1恰好具有一个。但是，由于您正在按顺序生成计数，因此您已经确定了i -b中有多少1。

唯一的技巧是如何找出b是什么。为此，我们使用另一种迭代技术：当您列出编号时，b在i时完全更改成为b ：

const countBits = function(n) {
    let arr = [0], bit = 1;
    for (let i = 1; i <= n; i++){
        if (i == bit + bit) bit += bit;
        arr.push(arr[i - bit] + 1);
    }
    return arr;
};

console.log(countBits(20));

该技术通常称为“动态编程”。从本质上讲，它采用递归定义并计算自下而上：它不是从所需的参数开始并递归到基本情况下，而是从基数开始，然后计算每个中间值，直到达到目标直到达到目标。在这种情况下，需要所有中间值，使我们不必考虑如何仅计算最小数量的中间值所需的中间值。

Answer 2

这样想：如果您知道一个数字x中有多少个，那么您立即知道x*2（相同）中有多少个（相同）和x*2+1（另一个）。由于您是按顺序处理数字，因此您只需将两个派生的计数推到结果并跳至下一个数字：

let b = [0, 1]

for (let i = 1; i <= N / 2; i++) {
    b.push(b[i])
    b.push(b[i] + 1)
}

由于我们一次将两个数字推到两个数字，因此，即使是n，结果都将是一次性的，您必须弹出之后的最后一个数字。

Answer 3

使用flool（）：

sum += Math.floor(value%2);
value = Math.floor(value/2);

我猜您的算法适用于某些打字语言，整数部门会导致整数

Answer 4

这是一种截然不同的方法，使用fold（例如array.prototype.reduce）通常称为展开。在这种情况下，我们从种子阵列开始，对其进行一些操作以产生下一个值，然后再出现，直到我们决定停止。

我们编写一个通用展开，然后将其与回调一起使用，该回调接受我们到目前为止发现的整个数组，以及next and 完成回调，然后选择是否停止（如果我们达到极限）或继续。无论哪种情况，它都称为两个回调之一。

看起来像这样：

const _unfold = (fn, init) =>
  fn (init, (x) => _unfold (fn, [...init, x]), () => init)

// Number of 1's in the binary representation of each integer in [`0 ... n`]
const oneBits = (n) => _unfold (
  (xs, next, done) => xs .length < n ? next (xs .length % 2 + xs [xs .length >> 1]) : done(),
  [0]
)

console .log (oneBits (20))

我有一个 github gist ，其中显示了这种模式的一些示例。

有趣的扩展名是封装阵列到长n位的处理，并使此功能变得微不足道。这不是这种_unfold的唯一用途，但这可能是常见的。看起来像这样：

const _unfold = (fn, init) =>
  fn (init, (x) => _unfold (fn, [...init, x]), () => init)

const unfoldN = (fn, init) => (n) => _unfold (
  (xs, next, done) => xs .length < n ? next (fn (xs)) : done (),
  init
)

const oneBits = unfoldN (
  (xs) => xs .length % 2 + xs [xs .length >> 1], 
  [0]
)

console .log (oneBits (20))

在这里，我们有两个助手功能，可以使OneBits写作非常微不足道。这些帮助者有许多潜在用途。

Answer 5

我这样做了，与位运算符

function countBits(n) {
    const arr = new Array(n + 1).fill(0);
    for(let i = 0; i <= n; i++){
        arr[i] = arr[i >>> 1] + (i & 1);
    }
    return arr;
};