EasyBlind75Bit Manipulation
Number of 1 Bits
Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).
Examples
Input
n = 11 (binary '1011')
Output
3
The input binary string 1011 has a total of three '1' bits.
Input
n = 128 (binary '10000000')
Output
1
The input binary string 10000000 has a total of one '1' bit.
Constraints
- •
1 <= n <= 2^31 - 1
Approaches
Check each bit by shifting right.
CodeT: O(32) = O(1) | S: O(1)
def hammingWeight(n):
count = 0
while n:
count += n & 1
n >>= 1
return countn & (n-1) removes the lowest set bit.
CodeT: O(k) where k = number of set bits | S: O(1)
def hammingWeight(n):
count = 0
while n:
n &= n - 1
count += 1
return countUse Python's built-in bit_count() method.
Diagram
n = 11 (1011)
11 & 10 = 10, count=1
10 & 01 = 00, count=2... wait
Actually: 11(1011) & 10(1010) = 10(1010), count=1
10(1010) & 01(1001) = 00(1000), count=2
08(1000) & 07(0111) = 00, count=3
Result: 3
CodeT: O(1) | S: O(1)
def hammingWeight(n):
return bin(n).count('1')Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Bit Shifting | O(32) = O(1) | O(1) | Check each bit by shifting right. |
| Brian Kernighan's Algorithm | O(k) where k = number of set bits | O(1) | n & (n-1) removes the lowest set bit. |
| Built-in Function | O(1) | O(1) | Use Python's built-in bit_count() method. |
Bit Shifting
T: O(32) = O(1)S: O(1)
Check each bit by shifting right.
Brian Kernighan's Algorithm
T: O(k) where k = number of set bitsS: O(1)
n & (n-1) removes the lowest set bit.
Built-in Function
T: O(1)S: O(1)
Use Python's built-in bit_count() method.
Common Mistakes
Using string conversion instead of bit operations
Not handling the case where n is 0
Shifting right without checking if n is still positive