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
Recommended Time and Space Complexity
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)