Number of 1 Bits

Problem

Given an unsigned 32-bit integer n, return the number of 1 bits it contains (its Hamming weight / population count). For example, 11 in binary is 1011, which has three 1 bits.

Examples

• 11 (00000000000000000000000000001011) → 3
• 128 (00000000000000000000000010000000) → 1
• 4294967293 (11111111111111111111111111111101) → 31

Constraints

• The input is a 32-bit integer.

Follow-up: if this function is called many times, can you make each call cheaper than scanning all 32 bits?

Think about it first

TL;DR

Brian Kernighan’s trick: clear the lowest set bit repeatedly and count the clears. O(set bits) time, O(1) space.

Approach 1 — Brute force: scan every bit

Read the lowest bit with n & 1, add it to the count, shift right, and repeat until n is 0.

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        count += n & 1      # the lowest bit, 0 or 1
        n >>= 1             # drop it, expose the next
    return count

Complexity: O(b) time where b is the index of the highest set bit (up to 32), O(1) space.

This visits every bit up to the top set bit, including all the zeros. For a sparse number like 128 (10000000) it examines eight positions to find one 1.

Approach 2 — Brian Kernighan: clear the lowest set bit

n & (n - 1) removes exactly the lowest set bit of n and leaves all other bits unchanged. Subtracting 1 turns the lowest set bit into 0 and flips every bit below it from 0 to 1; ANDing with the original n keeps the untouched high bits, clears that lowest set bit, and re-zeros the bits that got flipped up. Each application removes one 1, so the loop runs once per set bit and skips the zeros entirely. This is Brian Kernighan’s algorithm.

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= n - 1          # clear the lowest set bit
        count += 1
    return count

Walkthrough on n = 11 = 1011:

n is now 0, the loop ends, and we return 3. The loop ran 3 times, once per set bit, never touching the zero at position 2.

Complexity: O(s) time where s is the number of set bits (≤ 32), O(1) space. For sparse inputs this is faster than Approach 1.

Approach 3 — Built-in / lookup (the practical answer)

Python already counts bits, and for a fixed 32-bit width the count is O(1) regardless of the value. For the “called many times” follow-up, a precomputed table of byte popcounts turns each call into four lookups.

def hammingWeight(n: int) -> int:
    return bin(n).count("1")

A table-driven variant answering the follow-up (256-entry byte table, four bytes per 32-bit word):

_POPCOUNT = [bin(i).count("1") for i in range(256)]

def hammingWeight(n: int) -> int:
    total = 0
    while n:
        total += _POPCOUNT[n & 0xFF]   # count one byte via lookup
        n >>= 8
    return total

Complexity: O(1) for the 32-bit lookup version (four fixed byte lookups) after O(1) table setup; bin(...).count is O(b) but with tiny constants.

Common pitfalls

• while n vs a fixed 32 iterations: while n is faster for sparse inputs, but a signed negative value can loop forever. Mask or iterate a fixed 32 times in that case.
• Confusing n & (n - 1) (clear lowest set bit) with n & 1 (read lowest bit): they answer different questions.
• Operator precedence: count += n & 1 is fine, but n & 1 == 0 parses as n & (1 == 0). Parenthesize comparisons around bitwise operators.
• Python big ints: there is no fixed width, so a negative input conceptually has infinite leading ones. Mask with & 0xFFFFFFFF first if the caller might pass one.

Pattern takeaway

n & (n - 1) clears the lowest set bit. To iterate over, count, or find set bits efficiently, use it: the loop cost drops from one step per bit to one step per set bit.