191. Number of Bits

Reformulated question¶

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 this question 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.

Solve the problem with idiomatic python¶

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

Library alternative in modern Python:

class Solution:
    def hammingWeight(self, n: int) -> int:
        # Exact built-in for population count.
        return n.bit_count()

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

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("n", "expected"),
    [
        (1, 1),
        (2, 1),
        (3, 2),
        (4, 1),
        (7, 3),
        (8, 1),
        (11, 3),
        (128, 1),
        (255, 8),
        (256, 1),
        (1023, 10),
        (2147483645, 30),
        (2**31 - 1, 31),
    ],
)
def test_hamming_weight(n, expected):
    assert Solution().hammingWeight(n) == expected

Comment 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

Code¶

import pytest


class Solution:
    def hammingWeight(self, n: int) -> int:
        # Remove the lowest set bit each iteration.
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count


class SolutionBitCount:
    def hammingWeight(self, n: int) -> int:
        # Python built-in population count.
        return n.bit_count()


@pytest.mark.parametrize(
    ("n", "expected"),
    [
        (1, 1),
        (2, 1),
        (3, 2),
        (4, 1),
        (7, 3),
        (8, 1),
        (11, 3),
        (128, 1),
        (255, 8),
        (256, 1),
        (1023, 10),
        (2147483645, 30),
        (2**31 - 1, 31),
    ],
)
def test_hamming_weight(n, expected):
    assert Solution().hammingWeight(n) == expected
    assert SolutionBitCount().hammingWeight(n) == expected


Solution().hammingWeight(11)
Solution().hammingWeight(128)
Solution().hammingWeight(2147483645)

SolutionBitCount().hammingWeight(11)