Efficiently count the number of bits in an integer in JavaScript

Question

Let's say I have an integer I and want to get the count of 1s in its binary form.

I am currently using the following code.

Number(i.toString(2).split("").sort().join("")).toString().length; 

Is there a faster way to do this? I am thinking about using bitwise operators. Any thoughts?

NOTE: i is within the 32-bit limitation.

Answer 1

You can use a strategy from this collection of Bit Twiddling Hacks:

function bitCount (n) {    n = n - ((n >> 1) & 0x55555555)    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)    return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24  }    console.log(bitCount(0xFF)) //=> 8

Note that the above strategy only works for 32-bit integers (a limitation of bitwise operators in JavaScript).

A more general approach for larger integers would involve counting 32-bit chunks individually (thanks to harold for the inspiration):

function bitCount (n) {    var bits = 0    while (n !== 0) {      bits += bitCount32(n | 0)      n /= 0x100000000    }    return bits  }    function bitCount32 (n) {    n = n - ((n >> 1) & 0x55555555)    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)    return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24  }    console.log(bitCount(Math.pow(2, 53) - 1)) //=> 53

You could also use a regular expression:

function bitCount (n) {    return n.toString(2).match(/1/g).length  }    console.log(bitCount(0xFF)) //=> 8