LC 191 - Number of 1 Bits

Question

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight)

Example 1:

Input: n = 11
Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128
Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645
Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints:

• 1 <= n <= 231 - 1

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

Links

Question here and solution here

Solution

concept

The count the set bit in a number we can have 2 ways:

1. do a AND (&) operation with 1:
   1011
   & 0001
   0001
   this is because we can use the 1 to detect set bit.
2. we can also mod the number by 2: 1011 % 2 = 1 to get the last bit

We can then shift the number to the right, and we can have 2 ways:

1. shift the bit directly to the right using >> (preferred, it is a bit more efficient on CPU)
2. integer division by 2: 1011/2

AND Truth Table

A	B	A&B
F	F	F
F	T	F
T	F	F
T	T	T

code

class Solution:
    def hammingWeight(self, n: int) -> int:
        bin_str = "{0:b}".format(n)
        ans = 0
        for c in bin_str:
            if c == "1":
                ans += 1
        return ans 
    
class NeetSolution:
    def hammingWeight(self, n: int) -> int:
        """
        time complexity: O(n)
        space complexity: O(1)
        """
        ans = 0
        while n:
            # get last digit
            ans += n%2
            # bit shift to the right by 1
            n = n >> 1

        return ans

class NeetSolution:
    def hammingWeight(self, n: int) -> int:
        """
        this trick need logic AND n with n-1

        if the last bit of a number n is 1, then n-1 will flip the last bit to 0 and the rest remain the same
        if the last bit of a number n is 0, then n-1 will change accordingly e.g. 100000 -> 011111
        """
        res = 0
        while n:
            n &= n - 1
            res += 1
        return res 

Complexity

time: $O(1)$
space: $O(1)$