191. Number of 1 Bits

191

EasyBit ManipulationRepeatedly clearing the lowest set bit with n & (n - 1)Brian Kernighan bit clearing

Number of 1 Bits

Write a function that takes an integer and returns the number of set bits (1s) in its binary representation, also known as the Hamming weight.

Open official problem prompt ↗

In plain English

Count exactly how many 1 bits appear in the binary form of the given integer.

Picture it like this

Popping filled bubbles one at a time: each pop clears the lowest remaining filled bubble, and you count pops until the sheet is empty.

Example

Input: n = 11 (binary 1011)
Output: 3
Why: 1011 contains three 1 bits.

Constraints

The input is treated as an unsigned integer (up to 32 bits)1 <= n <= 2^31 - 1 in the modern signature

Pattern lesson

See the pattern, then code

Brian Kernighan bit clearing

↗

Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. Subtracting 1 from n flips its lowest set bit to 0 and turns all lower zeros into ones; ANDing with n clears exactly that lowest set bit. Each iteration removes one 1, so the loop runs once per set bit.

New words, made simpleKnow these before the algorithm

Hamming weight: The number of nonzero (set) bits in a value.
Lowest set bit: The rightmost 1 in the binary representation, isolable as n & -n and clearable as n & (n-1).

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Check every bit

Correct but always does 32 iterations regardless of how few bits are set.

Loop 32 times, testing n & 1 and shifting right.

Time O(32)Space O(1)

Best choiceBrian Kernighan clearing

Runs only as many times as there are 1s; the elegant optimal answer.

Repeatedly apply n &= n - 1 to drop the lowest set bit.

Time O(number of set bits)Space O(1)

The rule we keep true

Invariant

After each loop iteration, count equals the number of set bits already cleared, and n holds the original value with those lowest bits removed.

Why this is correct

Reasoning

n - 1 turns the lowest set bit into 0 and every bit below it into 1; ANDing with n keeps all higher bits unchanged while erasing that single lowest set bit. Since one set bit disappears per iteration, the number of iterations equals the Hamming weight.

The algorithm in three movesSay these aloud before coding

1Initialize count = 0

n=1011, count=0

2While n is nonzero, do n = n & (n - 1) to clear the lowest set bit

n&(n-1)=1010, count=1

3Increment count each time

n&(n-1)=1000, count=2

4Return count

n&(n-1)=0000, count=3

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

10110

10101

10002

00003

1 · Readn=1011

2 · Askn nonzero?

3 · Update statecount=0

4 · Resultenter loop

Key takeaway

Each n & (n-1) clears the rightmost 1; three clears empty 1011.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Counter
count accumulates how many set bits have been cleared.
2
Lines 4-6Clear-lowest-set-bit loop
n &= n - 1 removes one 1 per pass; the loop ends when n reaches 0.
3
Lines 7Return
count now equals the total number of set bits.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n = 0 returns 0 (loop never runs)
n with a single set bit returns 1
All bits set (e.g. 2^31 - 1) returns the count of those bits

Common beginner mistakes

Using n & (n - 1) but forgetting to increment count
In signed fixed-width languages, an infinite loop if arithmetic shift is used on a negative reinterpretation — not a concern in Python
Confusing this with counting trailing zeros or bit length

Check your understanding

Why does the loop run only as many times as there are set bits, not 32 times?

Number of 1 Bits

Number of 1 Bits

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Bit Manipulation