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

Bit Mask

def hammingWeight(self, n: int) -> int:
    mask = 1
    cnt = 0
    for _ in range(32):
        if mask&n: cnt += 1
        mask <<= 1
    return cnt

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