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

Question

I need to count the number of 1s in a binary representation of an integer. The two requirements are:

1) Must use table lookup 2) Must use XOR bitwise operator

So far, I think I have a table lookup that would work:

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;
};

This prints out something like:

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

I'm stumped on how I would use XOR to solve this problem (or why I would even use a lookup table). I feel like I could solve this easily by converting the int to a binary and then just looping through each character and summing up the 1s I see. However, the requirements are making it difficult.

Answer 1

This is only a partial hint, but it was too long for a comment. One of the things you can do with XOR is find the rightmost 1. You could then subtract this and do it again while keeping a count. This would tell you how many ones are in a number::

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

Maybe that's a little helpful. Not sure what the instructions are really after.