LeetCode 191. Number of 1 Bits

The Problem

Link to original problem on Leetcode.

Write a function that takes an unsigned integer and returns the number of 1 bits it has (also known as the Hamming weight).

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

My Solution

So, first of all, leetcode lies—it does not pass a binary string to the function (at least not when I write it in JavaScript), but passes a regular ‘ole number. Had they actually used a string, I would’ve first converted it to an integer with parseInt(n, 2), where n is the binary string and 2 is the radix, or numeral base, I want to convert to.¹

A naïve way to solve this would be to use bit shifting. We could compare n to 1 with AND, add the result to a counter, then shift n to the right. This will examine each bit in the number. Take 1011 for example.

count = 0

  1011
& 0001
------
  0001 => add 1 to count

  0101
& 0001
------
  0001 => add 1 to count

  0010
& 0001
------
  0000 => add 0 to count

  0001
& 0001
------
  0001 => add 1 to count

count === 3

In code:

const hammingWeight = n => {
	let count = 0;
	while (n) {
		count += n & 1;
		// Note: in JavaScript, use >>> for unsigned binary
		// integer shifting. For a signed 32-bit integer, a
		// negative number is marked with a 1 in the first
		// position. Using >> will preserve that one, causing
		// an infinite loop!
		n = n >>> 1;
	}
	return count;
};

Another more efficient way to solve this problem is by comparing n with n - 1 using AND. Every time you do this, mutate n to equal the result and increment a counter until n equals 0. What this does is clear the least significant digit with each iteration, meaning we only iterate as many times as there are 1’s. Here’s how this would look with the example 1011.

First loop
  1011 => n, which is 11
& 1010 => n - 1, which is 10
------
  1010 => set n to this
  count += 1

Second loop
  1010 => n
& 1001 => n - 1
------
  1000 => set n to this
  count += 1

Third loop
  1000 => n
& 0111 => n - 1
------
  0000 => n === 0, we can stop after this loop
  count += 1

Once n is zero, we’ve incremented our count variable once for each instance of a 1 in the binary representation of n. Each time we mutated n, we were setting it to it’s previous binary value but with the smallest 1 bit set to 0 instead. (E.g., 1011 to 1010 to 1000 and finally to 0000.) In code:

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

You can also write this recursively:

const hammingWeight = n => {
	return n ? hammingWeight(n & (n - 1)) : 0;
};