mediumDSA

How do you count the number of set bits in an integer?

Q: How do you count the number of set bits in an integer?

**Intuition.** A "set bit" is a 1 in the binary representation (also called the population count, or *popcount*). The slick trick is n & (n - 1) , which clears the **lowest** set bit each time — so you loop exactly as many times as there are 1s, not 32. 12 = 1100 (two 1s) 1 <rect x="156" y="34" width="36" height="40" rx="4" fill="#22c55e" fill-opacity="0.25" stroke="#22c55e"

725 views

Understand the problem

Explain bit counting.

bit-manipulation

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Brian Kernighan's algorithm

Run Playground

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


# --- demo ---  (builtin: bin(n).count('1') or n.bit_count())
print(count_bits(12))   # 2  (1100)
print(count_bits(7))    # 3  (0111)

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you compute the diameter of a binary tree?

How do you count connected components in an undirected graph?