如何使用 table 查找和 XOR 计算二进制中的 1？

Question

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

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

到目前为止，我认为我有一个可行的 table 查询：

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 来解决这个问题感到困惑（或者为什么我什至会使用查找 table）。我觉得我可以通过将 int 转换为二进制然后循环遍历每个字符并总结我看到的 1 来轻松解决这个问题。然而，要求使它变得困难。

Answer 1

这只是部分提示，但对于评论来说太长了。你可以用异或做的一件事是找到最右边的 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))

也许这有点帮助。不确定后面的说明是什么。

如何使用 table 查找和 XOR 计算二进制中的 1？

How to count 1s in binary using table lookup and XOR?

javascript

bitwise-operators

lookup-tables