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

Question

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

1( 必须使用表查找2( 必须使用XOR位运算符

到目前为止，我想我有一个可以工作的表查找：

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))

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