191. Number of 1 Bits

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

Example 1:

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

Example 2:

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

Example 3:

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

Follow up:

If this function is called many times, how would you optimize it?

Solution 1: Recursively Count Bits

class Solution:
    def hammingWeight(self, n: int) -> int:

        if n == 0:
            return 0

        return (n & 1) + self.hammingWeight(n >> 1)

This method recursively sums up the number of bits. There are two bit operations going on here:

n & 1 performs bitwise AND on the operands and returns the least significant bit in n
n >> 1 performs a left bitwise shift, which essentially divides the number by two and removes the last bit
- Example: 1010011 >> 1 => 101001

We combine these functions to sum up the bits. The algorithm is essentially to return the current bit, plus the bit next to it, plus the bit next to that one, and so on.

Solution 2: Iterative

class Solution:
    def hammingWeight(self, n: int) -> int:

        count = 0

        while n > 0:
            count += n & 1
            n >>= 1

        return count

This is the exact same algorithm as the previous solution, but is written iteratively instead of recursively.

Solution 3: Pythonic

class Solution:
    def hammingWeight(self, n: int) -> int:

        return bin(n).count('1')

This solutions takes advantage of built in Python methods. bin(n) converts the integer n into a binary string, then count(1)returns the number of times the '1' character is present in that string.

Solution 4: Brian Kernighan’s Algorithm

class Solution:
    def hammingWeight(self, n: int) -> int:

        count = 0

        while n > 0:
            n = n & (n-1)
            count += 1

        return count

This algorithm is a pretty big brained way to count set bits in an integer. It deals with the properties of bits when you subtract 1 from the number. You can read more about it in depth here.

Follow up

This question also asked: “If this function is called many times, how would you optimize it?”

There are a couple of different ways to do this. The first one would be to use memoization, and cache the number of set bits that you have already found.

An interesting (although less space-efficient) solution is to use a pre-generated lookup table that contains the number of set bits in all possible nibble values. Then, you can loop through the nibbles and count bits that way. This solution runs in constant time, because even the longest data type only contains 16 nibbles. an implementation of the nibble algorithm would look like this:

class Solution:
    def hammingWeight(self, n: int) -> int:

        nibble_counts = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]

        count = 0

        while n > 0:
            nib = n & 0xF
            count += nibble_counts[nib]
            n >>= 4

        return count

Notes

The most efficient solution out of all of these is actually the nibble one, running in 20ms, faster than ~98% of other submissions. Also interview story: in a Microsoft interview, someone wrote the Brian Kernighan algorithm on a whiteboard and told me to figure out what it did. It took me… a while.