Number of 1 Bits — InterviewPrepKit

Solving tips

Brian Kernighan's trick: n &= n - 1 clears the lowest set bit, so the loop runs once per set bit instead of once per bit, skipping all zeros.
Count each clear until n becomes 0; this is O(s) where s is the number of set bits (<= 32), O(1) space, faster than scanning all bits for sparse inputs.
For the 'called many times' follow-up, a precomputed 256-entry byte popcount table answers each 32-bit word in four lookups.
Pitfalls: don't confuse n & (n-1) with n & 1; and for possibly-negative inputs in Python, mask with & 0xFFFFFFFF or the while loop may not terminate as expected.

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

Hint 1

The direct way: look at each bit position, using `n & 1` to read the lowest bit and `n >>= 1` to move to the next. Count the `1`s.

Hint 2

There is a trick that skips the zeros entirely. `n - 1` flips the lowest set bit to `0` and turns every bit below it into `1`. What does `n & (n - 1)` then do to that lowest set bit?

Hint 3

`n & (n - 1)` clears the lowest set bit and leaves everything else. Repeat it until `n` becomes `0`; the number of iterations is exactly the number of set bits — so you loop once per `1`, not once per bit.

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

The naive intuition: read the lowest bit with n & 1, add it to the count, shift right, and repeat until n is 0.

class Solution:
    def hammingWeight(self, 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.

Why we can do better: this visits every bit up to the top set bit, including all the zeros. For a sparse number like 128 (10000000) it still churns through eight positions to find one 1.

Approach 2 — Brian Kernighan: clear the lowest set bit

The insight: n & (n - 1) removes exactly the lowest set bit of n and leaves all other bits alone. 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, kills that lowest set bit, and re-zeros the bits that got flipped up. So each application deletes one 1, and the loop runs once per set bit — the zeros are skipped entirely. (This is Brian Kernighan’s algorithm, the classic bit-counting trick.)

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

Walkthrough on n = 11 = 1011:

iteration	n (binary)	n - 1	n & (n - 1)	count
1	`1011`	`1010`	`1010`	1
2	`1010`	`1001`	`1000`	2
3	`1000`	`0111`	`0000`	3

n is now 0, loop ends, return 3. ✓ Notice we looped 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 much faster than Approach 1.

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

The insight: 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.

class Solution:
    def hammingWeight(self, 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)]

class Solution:
    def hammingWeight(self, 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 cleaner and faster for sparse inputs, but if the platform hands you a signed negative value you may loop forever — mask or iterate a fixed 32 times there.
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 ops.
Python big ints: there’s no fixed width, so a truly negative input has infinite leading ones conceptually — mask with & 0xFFFFFFFF first if the caller might pass one.

Pattern takeaway

n & (n - 1) clears the lowest set bit — the single most reusable bit idiom. Any time you want to iterate over, count, or find set bits efficiently, reach for it: the loop cost drops from “one step per bit” to “one step per set bit.”