# Number of 1 Bits

Math

## # Solution

lsb means least significant bit.

### # 1-liner Cheating

Python's built-in bin function converts n into a binary string. For instance, bin(12) would be '0b1100' and we can then count # of 1's in bin(n)[2:].

Complexity

time: $O(\log n)$
space: $O(\log n)$

def hammingWeight(self, n: int) -> int:
return bin(n)[2:].count('1')

1
2

### # Right Shift

In the while loop, get the lsb and increment cnt if equal to 1. Then right shift n.

Complexity

time: $O(\log n)$
space: $O(1)$

def hammingWeight(self, n: int) -> int:
cnt = 0
while n>0:
lsb = n&1
if lsb == 1:
cnt += 1
n = n >> 1
return cnt

1
2
3
4
5
6
7
8

def hammingWeight(self, n: int) -> int:
cnt = 0
for _ in range(32):
return cnt

1
2
3
4
5
6
7

### # Eliminate Lowest Set Bit

Eliminate lowest set bit in n by n = n & (n-1) and count the number of times we do this operation.

Complexity

time: $O(\log n)$
space: $O(1)$

def hammingWeight(self, n: int) -> int:
cnt = 0
while n>0:
cnt += 1
n &= n-1
return cnt

1
2
3
4
5
6