Blind 75.12 - Number of 1 Bits

Number of 1 bits.

Problem description

Taken directly from LeetCode.

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

Note:

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• The input must be a binary string of length 32.

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

Solution type

Doesn’t fit a category, just requires some thinking about what bit operations to use + how binary numbers work.

Solution

The easy solution is to repeatedly check the LSB and right shift until n goes to 0. I know there’s a nicer solution, so I’m going to try and think about that one…

Alright, nice and quick.

int hammingWeight(uint32_t n) {
    int weight = 0;
    while (n != 0) {
        n = n & (n - 1);
        weight++;
    }
    return weight;
}

The question I initially asked myself was “how can I move each 1 to the LSB every iteration?”, but the actual question to answer is even simpler: “how can I remove (zero out) the least significant bit that is set to 1 on each iteration?”. Consider the least significant bit that is set to 1 in an arbitrary-width integer:

0b...1000

We don’t care what the prefix is; we just want a way to set that 1 to a 0. To set something to zero, you probably want to use bitwise AND. We want to do a bitwise AND on this number using a second number that preserves the prefix but zeros out the rest. This would work great:

0b...0011

or

0b...0001

It just matters that we can consistently generate that second number and that it zeros out the 1. The way to do it ends up being to AND with n - 1, which in this scenario is

0b...0111

and after the bitwise AND results in

0b...0000.

n - 1 is the only number you can bitwise AND n with that consistently preserves the prefix to the least significant 1. If you aren’t convinced, try writing out n and n - 1 for a few different values of n in binary.

The number of 1s in the number is the same as the number of times we can perform this operation before reducing the value of n to 0. This results in a quick and easy solution that depends on the number of 1s instead of the width of the number. Take that, Python!.

I did remember there was some way to use n - 1 here, so this isn’t a spark of genius by any means; it’s me coming back to problems that I’ve trained on before.