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.

Not the first time requirements got in the way of good design. — ggorlen, Aug 01 '18 at 21:07
This feels like the quality problem a great education provides /s — zfrisch, Aug 01 '18 at 21:19
`const totallyUsed = {}[0^0];`, then do the code. "Must use" is just ridiculous, what counts as "use"? If it is some completely forced use that serves no other point, i think think the before mentioned does the job. — ASDFGerte, Aug 01 '18 at 21:19
Possible duplicate of [Efficiently count the number of bits in an integer in JavaScript](https://stackoverflow.com/questions/43122082/efficiently-count-the-number-of-bits-in-an-integer-in-javascript) — ASDFGerte, Aug 01 '18 at 21:58

score 2 · Accepted Answer · answered Aug 01 '18 at 21:27

2

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.

answered Aug 01 '18 at 21:27

Mark

90,562
7
108
148

this looks like it works! would you mind explaining `n -= n ^ (n & (n -1))` ? i don't get 1) why you subtract from n 2) why you subtract 1 from n 3) what & and ^ do in this case – bigpotato Aug 01 '18 at 21:31
towards finding bits in a number, there are tons of approaches - there is also the macro compacted table approach, but it doesn't use xor. There are others, which use xor somewhere on the line, but don't need a lookup table. One can e.g. forcefully use xor in the table method, but it's more of a joke then. – ASDFGerte Aug 01 '18 at 21:31
@Edmund if you are interested in learning more about bitwise operations in JavaScript give the MDN a documentation a read. Also keep in mind that casting something to a string is infinitely slower then a bitwise operation. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators – SudoKid Aug 01 '18 at 21:37
1

If one were to just implement it without restrictions, use this: `const countBits = n => { n = n - ((n >>> 1) & 0x55555555); n = (n & 0x33333333) + ((n >>> 2) & 0x33333333); return ((n + (n >>> 4) & 0xF0F0F0F) * 0x1010101) >>> 24; };` - see http://graphics.stanford.edu/~seander/bithacks.html (Counting bits set). Also note that WebAssembly offers access to the SSE instruction `__popcnt`, but WebAssembly to Javascript interop always has a lot of overhead, so it is not faster, when used primarily in JS. But all that is not what the question is about, it has those weird "must use" additions. – ASDFGerte Aug 01 '18 at 21:39
1

@Edmund `^` is XOR and `&` is bitwise AND. It's easiest to go through small numbers and watch the bits. For example starting with 6 `110` `&` 5 `101` gives you `100`. XOR that with the 6 gives you `10` or 4 the right most bit. Now subtract 4 from 6 which has the effect of removing the right most bit and do it again until you run out of bits. – Mark Aug 01 '18 at 21:41
That `n -= n ^ (n & (n -1))` could be written as `n ^= n & -n`, a bit simpler but still uses XOR – harold Aug 05 '18 at 10:06
@ASDFGerte That code's from C, which is strongly typed. In JS, you can get a significant speed boost by first coercing n to an int32 before the first operation, i.e. `n => { n = (n|0) - ...`. I tested some variations here: https://jsperf.com/fast-int32-bit-count – Doin Nov 09 '19 at 15:31

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

1 Answers1