javascript - 如何使用查表和异或来计算二进制中的 1？

Question

我需要计算整数的二进制表示形式中 1 的数量。 这两个要求是:

1) 必须使用表查找 2)必须使用异或按位运算符

到目前为止，我认为我有一个可行的表查找:

const generateLookupTable = (int) => {
  const range = Array.from({length: int}, (x,i) => i);
  const toBinary = (table, i) => {
    const binary = (i >>> 0).toString(2);
    table[i] = binary;
    return table;
  }

  const lookupTable = range.reduce(toBinary, {})
  return lookupTable;
};

这会打印出类似的内容:

generateLookupTable(7)
{0: "0", 1: "1", 2: "10", 3: "11", 4: "100", 5: "101", 6: "110"}

我对如何使用 XOR 来解决这个问题感到困惑(或者为什么我什至会使用查找表)。我觉得我可以通过将 int 转换为二进制，然后循环遍历每个字符并对我看到的 1 求和来轻松解决这个问题。然而，这些要求却让事情变得困难。

Answer 1

这只是部分提示，但对于评论来说太长了。您可以使用 XOR 做的事情之一是找到最右边的 1。然后您可以减去它并在保持计数的同时再次执行此操作。这会告诉你一个数字中有多少个::

function countOnes(n) {
    let count = 0
    while(n > 0) {
        n -= n ^ (n & (n -1))
        count++
    }
    return count
}

let n = 1709891;
console.log(countOnes(n))
console.log(n.toString(2))

n = 7
console.log(countOnes(n))
console.log(n.toString(2))

n = 9
console.log(countOnes(n))
console.log(n.toString(2))

也许这有点帮助。不确定指令的真正含义。