Loading…

easyBasicsSometimes asked

Count Set Bits

Basics · 6 min

Given a non-negative integer n, count the number of 1-bits in its binary representation (the Hamming weight).

In plain English

Repeatedly clear the lowest set bit with `n & (n-1)`, counting how many times until n becomes 0.

Examples

Example 1

Input: n = 7
Output: 3
Note: 111 has three 1s.

Example 2

Input: n = 8
Output: 1
Note: 1000.

Example 3

Input: n = 0
Output: 0
Note: No set bits.

Constraints

0 ≤ n ≤ 2^31 - 1

Clarifying questions1First question: Signed or unsigned / negative inputs?Explore questions

Q1.Signed or unsigned / negative inputs?
For negatives I'd use the unsigned/long form or a fixed-width loop.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Loop: while n != 0, do `n &= (n-1)` and increment a counter. Runs once per set bit — O(set bits).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know Kernighan's clear-lowest-bit loop.

Where candidates slip

A fixed 32-iteration scan, or forgetting to update n.

How to stand out

Explain why iterations equal set bits; mention Integer.bitCount as the library option.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Brian Kernighan's algorithm

TimeO(number of set bits)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What does `n & (n-1)` remove each time?

2Hint 2Explore hint

Count how many times you can clear a bit before n is 0.

3Hint 3Explore hint

Why is this better than checking all 32 bit positions?

A · Core idea

Count the 1-bits (Hamming weight) with Brian Kernighan's algorithm: repeatedly do n &= (n - 1), which clears the lowest set bit, and count how many times until n is 0.

Why the iteration count equals the bit count. Each n &= (n-1) removes exactly one set bit (the lowest), so the loop runs once per 1-bit. For a sparse number this is far fewer iterations than checking all 32 bits.

Why it beats the naive 32-iteration scan. A loop that tests each of the 32 bit positions always does 32 iterations; Kernighan's does only as many as there are set bits — e.g. 1 iteration for a power of two.

Built-ins exist (Integer.bitCount, bin(n).count('1')), but the Kernighan loop is the algorithm interviewers want to see and explains the clear-lowest-bit idiom.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 7 (111)

111

& 110 = 110

Statecount=1

Final result3

C · Code with teaching comments

solution.javaJava

Brian Kernighan's algorithm — optimal

2 teaching notes

1
public int countBits(int n) {
2
    int count = 0;
3
    while (n != 0) {
4
        // Clears the lowest set bit each iteration.
5
        n &= (n - 1);
6
        // One increment per set bit.
7
        count++;
8
    }
9
    return count;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(number of set bits) timeO(1) spaceOpen the invariant and proofExplore the proof

Built-ins exist (Integer.bitCount / bin(n).count('1')) but the Kernighan loop is the algorithm interviewers want to see.

ComplexityO(number of set bits) time, O(1) space — one iteration per set bit (≤ 32), each O(1).

E · Edge cases and pitfalls5n = 8 (1000) — One set bit → 1.Explore edge cases

Edge cases handled

n = 8 (1000)One set bit → 1.
n = 0No set bits → 0.
n = 2^31-1All low 31 bits set → 31.

Pitfalls

Looping a fixed 32 times unnecessarily.
Infinite loop if you forget to update n.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int countBits(int n) { int count = 0; while (n != 0) { n &= (n - 1); count++;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Looping a fixed 32 times unnecessarily.
Infinite loop if you forget to update n.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Kernighan bit-clear loop

Code pattern to memorize

count=0; while n: n &= n-1; count++

Rules to remember

1n &= n-1 clears a bit.
2Count iterations.
3Stops at 0.

Use this pattern when

Hamming weight
Bit-set counting

Interview takeaway

Each n &= n-1 removes one set bit — count the steps.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Kernighan bit-clear loop. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of 1 Bits
Coming soon
The LeetCode Hamming-weight version.
Power of Two
Set-bit count of exactly 1.

Same pattern

easyBasicsSometimes asked

Count Set Bits

Basics · 6 min

Given a non-negative integer n, count the number of 1-bits in its binary representation (the Hamming weight).

In plain English

Repeatedly clear the lowest set bit with `n & (n-1)`, counting how many times until n becomes 0.

Examples

Example 1

Input: n = 7
Output: 3
Note: 111 has three 1s.

Example 2

Input: n = 8
Output: 1
Note: 1000.

Example 3

Input: n = 0
Output: 0
Note: No set bits.

Constraints

0 ≤ n ≤ 2^31 - 1

Clarifying questions1First question: Signed or unsigned / negative inputs?Explore questions

Q1.Signed or unsigned / negative inputs?
For negatives I'd use the unsigned/long form or a fixed-width loop.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Loop: while n != 0, do `n &= (n-1)` and increment a counter. Runs once per set bit — O(set bits).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know Kernighan's clear-lowest-bit loop.

Where candidates slip

A fixed 32-iteration scan, or forgetting to update n.

How to stand out

Explain why iterations equal set bits; mention Integer.bitCount as the library option.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Brian Kernighan's algorithm

TimeO(number of set bits)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What does `n & (n-1)` remove each time?

2Hint 2Explore hint

Count how many times you can clear a bit before n is 0.

3Hint 3Explore hint

Why is this better than checking all 32 bit positions?

A · Core idea

Count the 1-bits (Hamming weight) with Brian Kernighan's algorithm: repeatedly do n &= (n - 1), which clears the lowest set bit, and count how many times until n is 0.

Built-ins exist (Integer.bitCount, bin(n).count('1')), but the Kernighan loop is the algorithm interviewers want to see and explains the clear-lowest-bit idiom.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 7 (111)

111

& 110 = 110

Statecount=1

Final result3

C · Code with teaching comments

solution.javaJava

Brian Kernighan's algorithm — optimal

2 teaching notes

1
public int countBits(int n) {
2
    int count = 0;
3
    while (n != 0) {
4
        // Clears the lowest set bit each iteration.
5
        n &= (n - 1);
6
        // One increment per set bit.
7
        count++;
8
    }
9
    return count;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(number of set bits) timeO(1) spaceOpen the invariant and proofExplore the proof

Built-ins exist (Integer.bitCount / bin(n).count('1')) but the Kernighan loop is the algorithm interviewers want to see.

ComplexityO(number of set bits) time, O(1) space — one iteration per set bit (≤ 32), each O(1).

E · Edge cases and pitfalls5n = 8 (1000) — One set bit → 1.Explore edge cases

Edge cases handled

n = 8 (1000)One set bit → 1.
n = 0No set bits → 0.
n = 2^31-1All low 31 bits set → 31.

Pitfalls

Looping a fixed 32 times unnecessarily.
Infinite loop if you forget to update n.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int countBits(int n) { int count = 0; while (n != 0) { n &= (n - 1); count++;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Looping a fixed 32 times unnecessarily.
Infinite loop if you forget to update n.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Kernighan bit-clear loop

Code pattern to memorize

count=0; while n: n &= n-1; count++

Rules to remember

1n &= n-1 clears a bit.
2Count iterations.
3Stops at 0.

Use this pattern when

Hamming weight
Bit-set counting

Interview takeaway

Each n &= n-1 removes one set bit — count the steps.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Kernighan bit-clear loop. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of 1 Bits
Coming soon
The LeetCode Hamming-weight version.
Power of Two
Set-bit count of exactly 1.

Same pattern