Recently, I came across a fun C++ challenge to count the number of set bits in an integer. Spending a lot of time in the browser, I wanted to re-implement it in JavaScript.

The challenge itself involves expressing integers in their binary representation. For those not familiar with base-10 to base-2 conversations, and what set bits are, check out the table below:

number	32	8	4	2	0	conversion	set bits
`4`	0	0	`1`	0	0	4¹ = 4	1
`4`	0	0	`1`	0	0	4¹ = 4	1
`8`	0	`1`	0	0	0	8¹ = 8	1
`7`	0	0	`1`	`1`	`1`	4¹+2¹+0¹ = 7	3
`35`	`1`	0	0	`1`	`1`	32¹+2¹+0¹ = 35	3

A note on JavaScript Numbers:

Under the hood, JavaScript represents all numbers as 64 bit floating point numbers. When we use a bitwise operator on a JavaScript number, it is transformed into a 32 bit integer.

We can demonstrate the conversion to a 32 bit integer by taking a JavaScript number, and performing a non mutating right bit shift by zero on it.

let x = 10;
y + 1 // = 6
(y + 1) >> 0 // = 6 >> 0 = 6.  Six bit shifted to the right by zero bits is still six

let y = 2147483647; // maximum value of a 32 bit integer.
y + 1 // = 2147483648, number increments correctly.
(y + 1) >> 0 // = -2147483648, bitwise right shift by zero. 32 bit integer overflows.

MDN, has a very good explanation of some of the quirks of this conversion:

Numbers with more than 32 bits get their most significant bits discarded. For example, the following integer with more than 32 bits will be converted to a 32 bit integer
Before: 11100110111110100000000000000110000000000001
After:              10100000000000000110000000000001

Don't expect bitwise operations to work as expected with numbers that need more than 32 bits of of memory, or any number over 2147483647.

// Show two different numbers from binary to base-10:

parseInt("11100110111110100000000000000110000000000001", 2); // 15872588537857
parseInt(            "10100000000000000110000000000001", 2); // 2684379137

// Show those same numbers bit shifted to the right by zero:

15872588537857 >> 0; // -1610588159
2684379137 >> 0; // -1610588159

// ¯\_(ツ)_/¯

Displaying integer bits in JavaScript:

To see how we can implement countSetBits, we will use the following helper function to display the binary representation of an integer:

const displayBits = n => {
    const bits = [];
    while(n) {
        bits.push(n & 1);
        n = n >> 1;
    }
    return bits.reverse();
}

Note: There is a far simpler way of displaying an integer to binary in JavaScript:

(5).toString(2); // "101"
(7).toString(2) // "111"

We will instead use the displayBits function above to discuss bitwise operators.

The function stores the ones and zeros in an Array called bits and returns it's reversed value.

In the loop, the function evaluates an integer n, and while n is not falsey it:

Evaluates n & 1, and pushes the result onto bits
Reassigns n to n >> 1

Evaluate `n & 1`, and push the result onto `bits`:

The bitwise & operator compares each bit in two integers and returns 1 if both bits are set to 1, otherwise it returns 0.

For example, using 5 and 7:

base 10	binary
`5`	`101`
`7`	`111`
`5 & 7`	`101`

And using 5 and 1 (our function uses n & 1):

base 10	binary
`5`	`101`
`1`	`1`
`5 & 1`	`1`

Using 7 and 1:

base 10	binary
`7`	`111`
`1`	`1`
`7 & 1`	`1`

Using 8 and 1:

base 10	binary
`8`	`1000`
`1`	`1`
`8 & 1`	`0`

We can see that when two ones in the same position overlap, the & operator returns a 1 in that position, otherwise it returns a 0.

When we perform a bitwise n & 1 we are only are interested in n's least significant bit (its rightmost bit), to see if it is a 0 or 1.

Because our loop runs bits.push(n & 1), we will either push a 0 or 1 into our bits array based on whether or not n's least significant bit is set or not.

Reassign `n` to `n >> 1`:

By reassigning n to n >> 1, we shift all of n's bits to the right by exactly one bit.

The integer 5 in binary is: 101
- 5 >> 1 is 10 (2 as a base-10 integer)
- 5 >> 1 >> 1 is 1 (1 as a base-10 integer)
- 5 >> 1 >> 1 >> 1 is 0 (0 as a base-10 integer)

Putting these two aspects of our loop together allow us to display base 10 integers in their binary format:

displayBits(5); // [1, 0, 1]
displayBits(9); // [1, 0, 0, 1]
displayBits(200); // [1, 1, 0, 0, 1, 0, 0, 0]

Counting Set Bits:

Modifying our displayBits function, we can change:

const bits = []; to let setBits = 0;
bits.push(n & 1); to setBits += (n & 1);
return bits.reverse(); to return setBits;

Making our new function look like this:

const countSetBits = n => {
    let setBits = 0;
    while(n) {
        setBits += (n & 1);
        n = n >> 1;
    }
    return setBits;
}

This will certainly work, and when we try it out for ourselves we can see it yields the correct results:

countSetBits(7); // 3
countSetBits(8); // 1

However, there is a faster (and much more interesting) way to implement this function:

A More Efficient Way:

const countSetBits = n => {
    let setBits = 0;
    while(n) {
        n &= n - 1;
        setBits ++;
    }
    return setBits;
}

The first thing to notice is that in our while loop we are always incrementing setBits by 1. This means that the while loop only iterates m times, where m is the number of set bits. In our original implementation, our loop always ran n times, where n is the number of bits taken to express the integer.

Considering the integer 274,877,906,945 which expressed in binary is 100000000000000000000000000000000000001:

Our original implementation's while loop would have to run through 39 iterations, one for each bit. In our new implementation however, only 2 iterations are needed.

Granted, this scenario is somewhat hyperbolic, but it still demonstrates the potential time complexity savings of the second algorithm.

The "special sauce" that gives the second algorithm its advantage lies in the operation, n &= n -1;, which reassigns n to the bitwise & comparison between itself and n - 1.

Starting with n = 65, which is 1000001 in binary, we can see how the algorithm terminates in just two iterations:

Iteration	n	n - 1	n & (n - 1)
1	`1000001`	`1000000`	`1000000`
2	`1000000`	`0111111`	`0000000`
3	`0000000`	N/A	N/A

We can see that by the time the third iteration wants to start, n is already 0, so the iteration never fires and the function exits.

# Bit Twiddling

Bit Twiddling in JavaScript