LeetCode 191. Number of 1 Bits (Hamming Weight)

Question: https://leetcode.com/problems/number-of-1-bits

This is an interesting bit manipulation problem. I have come up with two solutions, but the third one is quite out of expectation. Speed comparison between all three solutions is also quite interesting.

1. The below solution is what normal people would come up with when first looking at the problem. We simply find all the bits of a number and increment the count whenever a bit 1 is encountered. The speed and memory usage are 20ms and 12MB. The asymptotic efficiency is O(logN)

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        # Normal People Solution
        count = 0
        while n // 2!=0:
            if n % 2 == 1:
                count += 1
            n //= 2
        if n == 1:
            count += 1
        return count

2. We can also use a 32-bit long mask to pick out one bit at a time and count the bit if it's 1. It's an easy application of the idea that when a number, n,  AND with a number that is an exponential of 2, we will simply pick out the bit of n in the corresponding location. For instance, 5 = 101, when AND with 4=100, we get 101 & 100 = 100 = 4. Speed and memory usage are 20ms and 11.9MB.

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        for i in range(32):
            mask = 2**i
            if (n & mask)==mask:
                count +=1
        return count

Instead of raising 2^i to get the mask, we can also use shift operator like it is below. Shifting a bit to the right simply multiply a number by 2. Surprisingly, there is no improvement in speed and memory: 24 ms and 11.9MB.

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        mask = 1
        for i in range(32):
            if (n & mask)==mask:
                count +=1
            mask <<= 1
        return count

3. Now here comes the most unexpected solution. First of all, what does n&n-1 do? It flips the least significant bit. Why does it flip the least significant bit? Think of a number like 6 = 110. Comparing this to 6-1=5=101. We see that the part to the right of the least significant bit in 6, 110 got subtracted by 1. yielding 101. This is what happened when we subtract 1 from any number n, we are subtracting 1 of the part to the right of the least significant bit leaving the part to the left intact. What happens when we AND n with n-1? We know that the part to the left is intact, because x & x = x. How about the part to the right? well, we know the part to the right will definitely be of the form (100...), let's call this x. Then, x-1 is of the form (011....). Therefore, x&x-1 becomes (00000....)! It is equivalent to flipping the least significant bit from 1 to 0! The algorithm below just keeps on flipping the least significnt bit until it reaches 0. The speed and memory is 16ms and 11.7MB. Faster with lower memory usage!

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """        
        # Superman Solution
        count = 0
        while n != 0:
            n &=n-1
            count += 1
        return count

Related Questions:
Number Complement: https://monkeyinvestment.blogspot.com/2020/03/leetcode-476-number-complement.html