191. Number of Bits

Problem¶

Count how many 1 bits are in the binary form of a positive integer n.

Example:

n = 11 -> bin = 1011 -> answer = 3

Key trick¶

Use the bit trick:

n &= n - 1

Each use removes the lowest set bit, so the number of loop iterations is exactly the answer.

Trap¶

• Using division/modulo works, but it is less idiomatic for bit problems.
• Confusing decimal digits with binary bits.
• For the follow-up, recomputing from scratch every time instead of using a cache or lookup table.
• In Python, negative numbers have tricky infinite-sign-bit behavior, but this problem gives positive n.

Why is it interesting?¶

• It tests whether you know a classic bit manipulation identity.
• It gives a better-than-naive loop: \(O(\text{number of set bits})\) instead of \(O(\text{number of bits})\).
• It opens the door to practical optimizations for repeated calls.

Python solution¶

class Solution:
    def hammingWeight(self, n: int) -> int:
        # Remove one set bit at a time.
        cnt = 0
        while n:
            n &= n - 1
            cnt += 1
        return cnt

    def hammingWeight_2(self, n: int) -> int:
        return n.bit_count()

Comment on my solution¶

• Your solution is correct.
• It is a base-2 digit count using % 2 and // 2, so it runs in \(O(\log n)\) bit positions.
• The usual interview improvement is n &= n - 1, which is more idiomatic for bit manipulation and can be faster when n has few 1 bits.
• A tiny cleanup is to update n directly instead of copying into q.

import pytest

class Solution:
    def hammingWeight(self, n: int) -> int:
        # n given in base 10
        weight = 0
        q = n

        while q:
            r = q % 2
            q //= 2
            weight += r

        return weight

@pytest.mark.parametrize(
    ("n", "expected"),
    [(11, 3), (128, 1), (2147483645, 30)]
)
def test_hammingWeight(n, expected):
    assert Solution().hammingWeight(n) == expected

Extra¶

n &= n - 1 bit trick example¶

An example (from me) to see the n &= n - 1 trick in action:

n = 50
bin(n) # "0b110010"
count = 0

while n:
    print("------------")
    print(f"          n: {bin(n)}")
    print(f"      n - 1: {bin(n - 1)}")
    print(f"n & (n - 1): {bin(n & (n - 1))}")
    n = n & (n - 1)
    count += 1
# ------------
#           n: 0b110010
#       n - 1: 0b110001
# n & (n - 1): 0b110000
# ------------
#           n: 0b110000
#       n - 1: 0b101111
# n & (n - 1): 0b100000
# ------------
#           n: 0b100000
#       n - 1: 0b11111
# n & (n - 1): 0b0

count # 3