Number of 1 Bits

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).

Shell

The gist of the problem

Like always, let’s begin with intuition (see my thoughts on intuition as more important than analysis). The actual problem we have is analyzing a string of binary integers (0s or 1s) to count the number of 1s. Conceptually we are observing a fixed size binary string and trying to figure out how many of those binary integers are 1. Imagine, if you will, you are floating above a fixed size series of 1s and 0s. If you want to know how many of those digits are 1s and how many are 0s, how would you do it?

You could just look at each of them and count in your head. That is the intuitively obvious approach and that is what we should do here too, at least at first. This is pretty simple with a bit of bit fiddling.

Pretty simple. Can we do better? Should we do better? Maybe, depending on the context and frequency with which we need to do the computation we might benefit from some optimization. But more importantly, how would we get there? Can we prove we cannot get there?

I’m copping out here. In an interview I might suggest, if we really were concerned about runtime complexity, some form of precomputation or hashing since we have only 32 possible results and a wide input space. Although most likely this would be a simple screening question or not asked at all.

class Solution {
public:
    int hammingWeight(uint32_t n) {   
    }
};

#define BITMASK(m, n) m & 1<<n

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int h = 0;
        for (int i = 0; i < 32; i++) {
            if (BITMASK(n, i)) {
                h++;
            }
        }
        return h;
    }
};