JavaScript实现LeetCode Counting Bits题结果错误排查

给定整数n，需要返回长度为n+1的数组ans，对于每个满足0 <= i <= n的i，ans[i]的值为i的二进制表示中1的个数。
现有实现输入n=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));

JavaScript中/运算符执行的是浮点数除法，不是整数除法。以i=1的计算过程为例：

1. 初始value=1，第一次循环：sum += 1%2得到sum=1，执行value /=2后value为0.5，不等于0，循环继续
2. 后续循环中value会依次变为0.25、0.125……直到浮点数下溢为0才会终止，过程中所有小数部分取余2的结果都会被累加到sum中，最终sum值约等于2，导致结果错误。

将浮点数除法替换为整数除法即可，可选写法如下：

• value = Math.floor(value / 2)：对除法结果向下取整
• value = value >> 1：对整数执行右移1位操作，等价于除以2取整
• value = ~~(value / 2)：通过双按位非操作实现整数取整

var countBits = function(n) {
    var arr = [0];
    for (var i = 1; i <= n; i++){
        var sum = 0;
        var value = i;
        while(value != 0){
            sum += value % 2;
            // 替换为整数除法
            value = Math.floor(value / 2);
        }
        arr.push(sum);
    }
    return arr;
};

console.log(countBits(2)); // 输出 [0,1,1]，符合预期
console.log(countBits(3)); // 输出 [0,1,1,2]，符合预期

内容的提问来源于stack exchange，提问作者QPAO