# Number of 1 Bits ## # 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')


### # 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


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


### # Eliminate Rightmost 1-bit

Eliminate rightmost 1-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

Last Updated: 7/19/2020, 3:45:14 PM