Number of One Bits

Problem Statement

You are given an unsigned integer n. Return the number of 1 bits in its binary representation.

You may assume n is a non-negative integer which fits within 32-bits.

Example 1:

# Input: n = 0b00000000000000000000000000010111
# (In decimal: 23)
Input: n = 23


Output: 4

Example 2:

# Input: n = 0b01111111111111111111111111111101
# (In decimal: 2147483645)
Input: n = 2147483645


Output: 31

You should aim for a solution with O(1) time and O(1) space.

Hint 1

How can you isolate the rightmost bit of a number?

Hint 2

Consider using bitwise AND and right shift operators.

Hint 3

The expression n & (n - 1) clears the least significant bit of n.

Solution

Bit Mask - I

def hamming_weight(n: int) -> int:
    res = 0
    for i in range(32):
        if (1 << i) & n:
            res += 1
    return res

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

Bit Mask - II

def hamming_weight(n: int) -> int:
    res = 0
    while n:
        res += 1 if n & 1 else 0
        n >>= 1
    return res

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)