LeetCode Count number of set bits solution

Question

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

int hammingWeight(uint32_t n) {
        int count = 0;
        while(n>0){
            count+=n&1;
            n>>=1;
        }
        return count;
    }

Can you come up with a better method?

One gentleman came up with this

int hammingWeight(uint32_t n) {
    int count = 0;

    while (n) {
        n &= (n - 1);
        count++;
    }

    return count;
}

How does one come up with such creative solutions?

And do you have a better one or any improvements I can make to my solution?

Answer 1

(Because of the way Code Review works, only your code can be reviewed. Therefore, I will not say anything on the code written by "one gentleman".)

The first thing I see is: use consistent indentation and add spaces. Your code becomes much more readable if you format it like this:

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n > 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Also, it is probably a good idea to use std::uint32_t instead of uint32_t in C++.

You can make this function constexpr and noexcept. Simple computations like this can be done at compile time, and benefit from inlining.

This function can also be generalized to take any unsigned integer type. A template version may look like:

template <typename T, std::enable_if_t<std::is_integral_v<T> && std::is_unsigned_v<T>>>
constexpr int hammingWeight(T n) noexcept
{
    // the implementation is the same
}

The implementation is good enough and very readable IMO. You don't have to get very creative unless measuring reveals the necessity of optimization.

In C++20, we have a standard function for this — std::popcount, in header <bit>.