Sign in
Skip to solution
mediumDSA

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

725 views
01

Understand the problem

Explain bit counting.

bit-manipulation
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Repeatedly apply n &= n - 1, which clears the lowest set bit, counting iterations — runs in O(number of set bits). Many CPUs/languages also expose a popcount builtin.

Solution ready — 2 min read

Classified // press E to declassify

04

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)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 52 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track