Number of 1 Bits (LeetCode 191)
Given a positive integer n, count how many bits equal 1 appear in its binary form — this count is known as the number's Hamming weight.
A set bit refers to a bit in the binary representation of a number that is equal to 1.
Worked Examples
n = 113n = 11 is 1011 in binary, which contains three 1-bits.n = 1281n = 128 is 10000000 in binary, which contains only one 1-bit.n = 214748364530n = 2147483645 is 1111111111111111111111111111101 in binary, which contains thirty 1-bits.⚖️Formal Constraints & Bounds
1 <= n <= 231 - 1
Core Insight
Subtracting 1 from n flips all bits up to and including the lowest set bit. Therefore, n & (n - 1) resets the least significant 1-bit to 0 in a single operation, eliminating the need to shift through 32 full bits.
Real-World Scenario & Production Applications
Network packet error detection (parity checking), population count (popcount) in cryptography & hash functions, bitboard piece evaluation in chess engines.
Step-by-Step Execution Trace Table
| Iteration | Current n (Binary) | n - 1 (Binary) | n & (n - 1) | Set Bit Count |
|---|---|---|---|---|
| 1 | 11 (1011₂) | 10 (1010₂) | 10 (1010₂) | 1 |
| 2 | 10 (1010₂) | 9 (1001₂) | 8 (1000₂) | 2 |
| 3 | 8 (1000₂) | 7 (0111₂) | 0 (0000₂) | 3 (Terminates n = 0) |
The Math, Step by Step
1. The number the code counts
The Hamming weight of is the number of 1 bits in its binary form. The code does not look at every bit. It removes one 1 bit per round, and counts the rounds until is 0.
2. What n & (n - 1) does to one number
Write in binary. Its lowest 1 bit has some number of 0 bits to its right. Call everything to the left of that 1 bit the prefix :
Subtracting 1 borrows from the lowest 1 bit. That bit becomes 0, and the zeros to its right become 1s. The prefix does not change:
& keeps a bit only where both numbers have a 1:
| Part of the bits | In | In | In n & (n - 1) |
|---|---|---|---|
| the prefix | |||
| the lowest 1 bit | 1 | 0 | 0 |
| the bits to its right | all 0 | all 1 | all 0 |
So n & (n - 1) is with its lowest 1 bit cleared, and every other bit unchanged. This is Kernighan's bit trick.
3. Why the loop runs once per 1 bit
Each round clears exactly one 1 bit and changes no other bit. So after rounds, where is the Hamming weight, all 1 bits are gone and is 0. The loop while n > 0 then stops, and count equals .
The loop runs times, not once per bit position. For , which has 8 bit positions, it runs only once.
4. The stopping condition
The loop stops at , which has no 1 bit. For the rule of part 2 does not apply, because 0 has no lowest 1 bit. The loop never computes 0 & (0 - 1), because while n > 0 checks first. The problem guarantees , so the loop runs at least once.
The input is at least 1 and at most , so is never negative. If it were, while n > 0 would be false at once, and the code would return 0.
5. Example 1 by hand
n = 11, which is 1011 in binary.
| Round | n | n - 1 | n & (n - 1) | count |
|---|---|---|---|---|
| 1 | 1011 | 1010 | 1010 | 1 |
| 2 | 1010 | 1001 | 1000 | 2 |
| 3 | 1000 | 0111 | 0000 | 3 |
Each row clears the lowest 1 bit: bit 0, then bit 1, then bit 3. After round 3, n is 0, so the loop stops. The code returns 3, the expected output.
6. Example 2 by hand
n = 128, which is 10000000 in binary. Then n - 1 = 127 is 01111111, and n & (n - 1) is 0. The loop runs once, and the code returns 1, the expected output.
7. From the math to the code
| Math | In hammingWeight |
|---|---|
| no rounds yet | count = 0 |
| stop when no 1 bit is left | while n > 0: |
| clear the lowest 1 bit | n &= (n - 1) |
| one 1 bit removed | count += 1 |
| the Hamming weight | return count |
The loop runs once per 1 bit, at most 31 times for this input range. So the code takes time, where is the number of 1 bits, and space.
| 1 | count = 0 |
| 2 | while n > 0: |
| 3 | n &= (n - 1) |
| 4 | count += 1 |
| 5 | return count |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The line n &= (n - 1) clears one bit of n, and at first it is not clear which bit or why. A physical picture shows the mechanism step by step.
💡 The Analogy: A Row of Light Switches
Picture your number as a row of light switches, ON (1) or OFF (0). You want to count how many switches are ON, but instead of checking all 32 switches one by one, you want a shortcut that only takes as many steps as there are ON switches.
- Borrowing (
n - 1): Subtracting 1 finds the rightmost ON switch, flips it OFF, and flips every switch to its right ON (like borrowing in grade-school subtraction ripples through the digits). Everything to the left of that switch is untouched. - Cancelling (
n & (n - 1)): Now AND the borrowed row against the original row. A switch stays ON after the AND only if it was ON in both rows. The rightmost ON switch is OFF in the borrowed row, so it ends up OFF. Everything the borrow flipped ON to its right was already OFF in the original row, so those end up OFF too. Every switch to the left never changed, so it keeps its value. Net effect: exactly one switch — the rightmost ON one — gets cleared, and nothing else moves.
🔑 The Key Idea in the Code
Because each pass clears exactly one ON switch, the loop runs exactly K times — the number of 1 bits — never the full 32, no matter how large n is.
Fixed 32-iteration loop vs Kernighan's optimization: Looping 32 times does redundant work for sparse bitmasks.
n &= (n - 1)terminates as soon as all set bits are cleared.Signed infinite loop in typed languages: In C++/Java,
n >>= 1on signed negative values fills the MSB with 1s indefinitely. Use unsigned types (uint32_t) or logical shift.Using modulo
% 2and division// 2: Modulo and division require ALU division circuits; bitwisen & 1andn >>= 1are single-cycle bitwise instructions.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Counting binary 1-bits, bit population count, register parity checks.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: count plus the set bits still in n always equals the set bits of the original n. The loop ends when n is 0, so count is then the answer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A shift loop (
count += n & 1; n >>= 1) runs once per bit position up to the highest 1, up to 31 rounds here; Kernighan's loop runs once per set bit.while n > 0, not a fixedfor _ in range(32): the loop must stop once the last set bit is cleared, orcountkeeps growing (n = 11would give 32, not 3).return n > 0 and (n & (n - 1)) == 0inis_power_of_two:0 & -1is also0, so withoutn > 0the answer for0isTrue.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Kernighan's Bit Trick. I keep
count = 0and, whilenis above zero, runn &= (n - 1)and add one tocount. Subtracting one turns the lowest set bit into a zero and the zeros below it into ones, so the AND removes exactly that bit and keeps every higher bit. That meanscountplus the bits left innalways equals the answer, and whennreaches zero,countis it. The loop condition is the part to get right: it stops as soon as the last set bit is gone, instead of walking all 32 positions. Time is O(K) for K set bits, at most 31 here, and space isO(1).
Complexity & Mathematical Proof
O(K), K = number of set bits (<= 32)
Look at the execution steps: each round of while n > 0 runs n &= (n - 1), which removes one set bit, so the loop runs exactly K times, where K is the number of set bits.
O(1)
Look at memory allocations: Call stack uses O(1) Iterative. Single integer counter register.
Derivation Progression
1 set bit removed per round ⟹ K rounds
Each n &= (n - 1) removes one set bit, so after K rounds n is 0.
count += 1 per set bit
Counts exactly the number of set bits.
while n > 0 fails at n = 0
The loop stops right after the last set bit is cleared; no round is spent on a zero bit.
Variable Definitions
Number of set bits in n (at most 31, since LC 191 has n ≤ 2^31 - 1)
Memory Architecture & Bounds
O(1) Iterative
O(1) CPU registers
O(1) Set bit count integer
Boundary Best / Worst Cases
: n a power of two (1 round).
: one round per set bit.
= : n = 2^{31} - 1 (31 rounds).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
When I look at this problem statement, the trigger phrase is "number of '1' bits" (also known as Hamming Weight or Population Count / popcount). A loop over every bit position works, but the count only needs one step per set bit: Kernighan's Bit Trick, n & (n - 1). At scale the same count runs word by word over large bitmaps, where each sparse word finishes in a few rounds.
LeetCode gives , so n has at most 31 set bits and the loop runs at most 31 times. It stops as soon as n reaches 0.
If an API can pass a negative value (a signed 32-bit register holding unsigned data), mask it to 32 bits first: while n > 0 returns 0 at once for a negative number, and while n: never ends on a negative Python int. Edge cases: (1 round) and (31 rounds).
Number of 1 Bits (LeetCode 191)
Given a positive integer n, count how many bits equal 1 appear in its binary form — this count is known as the number's Hamming weight.
A set bit refers to a bit in the binary representation of a number that is equal to 1.
Worked Examples
n = 113n = 11 is 1011 in binary, which contains three 1-bits.n = 1281n = 128 is 10000000 in binary, which contains only one 1-bit.n = 214748364530n = 2147483645 is 1111111111111111111111111111101 in binary, which contains thirty 1-bits.⚖️Formal Constraints & Bounds
1 <= n <= 231 - 1
Core Insight
Subtracting 1 from n flips all bits up to and including the lowest set bit. Therefore, n & (n - 1) resets the least significant 1-bit to 0 in a single operation, eliminating the need to shift through 32 full bits.
Real-World Scenario & Production Applications
Network packet error detection (parity checking), population count (popcount) in cryptography & hash functions, bitboard piece evaluation in chess engines.
Step-by-Step Execution Trace Table
| Iteration | Current n (Binary) | n - 1 (Binary) | n & (n - 1) | Set Bit Count |
|---|---|---|---|---|
| 1 | 11 (1011₂) | 10 (1010₂) | 10 (1010₂) | 1 |
| 2 | 10 (1010₂) | 9 (1001₂) | 8 (1000₂) | 2 |
| 3 | 8 (1000₂) | 7 (0111₂) | 0 (0000₂) | 3 (Terminates n = 0) |
The Math, Step by Step
1. The number the code counts
The Hamming weight of is the number of 1 bits in its binary form. The code does not look at every bit. It removes one 1 bit per round, and counts the rounds until is 0.
2. What n & (n - 1) does to one number
Write in binary. Its lowest 1 bit has some number of 0 bits to its right. Call everything to the left of that 1 bit the prefix :
Subtracting 1 borrows from the lowest 1 bit. That bit becomes 0, and the zeros to its right become 1s. The prefix does not change:
& keeps a bit only where both numbers have a 1:
| Part of the bits | In | In | In n & (n - 1) |
|---|---|---|---|
| the prefix | |||
| the lowest 1 bit | 1 | 0 | 0 |
| the bits to its right | all 0 | all 1 | all 0 |
So n & (n - 1) is with its lowest 1 bit cleared, and every other bit unchanged. This is Kernighan's bit trick.
3. Why the loop runs once per 1 bit
Each round clears exactly one 1 bit and changes no other bit. So after rounds, where is the Hamming weight, all 1 bits are gone and is 0. The loop while n > 0 then stops, and count equals .
The loop runs times, not once per bit position. For , which has 8 bit positions, it runs only once.
4. The stopping condition
The loop stops at , which has no 1 bit. For the rule of part 2 does not apply, because 0 has no lowest 1 bit. The loop never computes 0 & (0 - 1), because while n > 0 checks first. The problem guarantees , so the loop runs at least once.
The input is at least 1 and at most , so is never negative. If it were, while n > 0 would be false at once, and the code would return 0.
5. Example 1 by hand
n = 11, which is 1011 in binary.
| Round | n | n - 1 | n & (n - 1) | count |
|---|---|---|---|---|
| 1 | 1011 | 1010 | 1010 | 1 |
| 2 | 1010 | 1001 | 1000 | 2 |
| 3 | 1000 | 0111 | 0000 | 3 |
Each row clears the lowest 1 bit: bit 0, then bit 1, then bit 3. After round 3, n is 0, so the loop stops. The code returns 3, the expected output.
6. Example 2 by hand
n = 128, which is 10000000 in binary. Then n - 1 = 127 is 01111111, and n & (n - 1) is 0. The loop runs once, and the code returns 1, the expected output.
7. From the math to the code
| Math | In hammingWeight |
|---|---|
| no rounds yet | count = 0 |
| stop when no 1 bit is left | while n > 0: |
| clear the lowest 1 bit | n &= (n - 1) |
| one 1 bit removed | count += 1 |
| the Hamming weight | return count |
The loop runs once per 1 bit, at most 31 times for this input range. So the code takes time, where is the number of 1 bits, and space.
| 1 | count = 0 |
| 2 | while n > 0: |
| 3 | n &= (n - 1) |
| 4 | count += 1 |
| 5 | return count |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The line n &= (n - 1) clears one bit of n, and at first it is not clear which bit or why. A physical picture shows the mechanism step by step.
💡 The Analogy: A Row of Light Switches
Picture your number as a row of light switches, ON (1) or OFF (0). You want to count how many switches are ON, but instead of checking all 32 switches one by one, you want a shortcut that only takes as many steps as there are ON switches.
- Borrowing (
n - 1): Subtracting 1 finds the rightmost ON switch, flips it OFF, and flips every switch to its right ON (like borrowing in grade-school subtraction ripples through the digits). Everything to the left of that switch is untouched. - Cancelling (
n & (n - 1)): Now AND the borrowed row against the original row. A switch stays ON after the AND only if it was ON in both rows. The rightmost ON switch is OFF in the borrowed row, so it ends up OFF. Everything the borrow flipped ON to its right was already OFF in the original row, so those end up OFF too. Every switch to the left never changed, so it keeps its value. Net effect: exactly one switch — the rightmost ON one — gets cleared, and nothing else moves.
🔑 The Key Idea in the Code
Because each pass clears exactly one ON switch, the loop runs exactly K times — the number of 1 bits — never the full 32, no matter how large n is.
Fixed 32-iteration loop vs Kernighan's optimization: Looping 32 times does redundant work for sparse bitmasks.
n &= (n - 1)terminates as soon as all set bits are cleared.Signed infinite loop in typed languages: In C++/Java,
n >>= 1on signed negative values fills the MSB with 1s indefinitely. Use unsigned types (uint32_t) or logical shift.Using modulo
% 2and division// 2: Modulo and division require ALU division circuits; bitwisen & 1andn >>= 1are single-cycle bitwise instructions.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Counting binary 1-bits, bit population count, register parity checks.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: count plus the set bits still in n always equals the set bits of the original n. The loop ends when n is 0, so count is then the answer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A shift loop (
count += n & 1; n >>= 1) runs once per bit position up to the highest 1, up to 31 rounds here; Kernighan's loop runs once per set bit.while n > 0, not a fixedfor _ in range(32): the loop must stop once the last set bit is cleared, orcountkeeps growing (n = 11would give 32, not 3).return n > 0 and (n & (n - 1)) == 0inis_power_of_two:0 & -1is also0, so withoutn > 0the answer for0isTrue.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Kernighan's Bit Trick. I keep
count = 0and, whilenis above zero, runn &= (n - 1)and add one tocount. Subtracting one turns the lowest set bit into a zero and the zeros below it into ones, so the AND removes exactly that bit and keeps every higher bit. That meanscountplus the bits left innalways equals the answer, and whennreaches zero,countis it. The loop condition is the part to get right: it stops as soon as the last set bit is gone, instead of walking all 32 positions. Time is O(K) for K set bits, at most 31 here, and space isO(1).
Complexity & Mathematical Proof
O(K), K = number of set bits (<= 32)
Look at the execution steps: each round of while n > 0 runs n &= (n - 1), which removes one set bit, so the loop runs exactly K times, where K is the number of set bits.
O(1)
Look at memory allocations: Call stack uses O(1) Iterative. Single integer counter register.
Derivation Progression
1 set bit removed per round ⟹ K rounds
Each n &= (n - 1) removes one set bit, so after K rounds n is 0.
count += 1 per set bit
Counts exactly the number of set bits.
while n > 0 fails at n = 0
The loop stops right after the last set bit is cleared; no round is spent on a zero bit.
Variable Definitions
Number of set bits in n (at most 31, since LC 191 has n ≤ 2^31 - 1)
Memory Architecture & Bounds
O(1) Iterative
O(1) CPU registers
O(1) Set bit count integer
Boundary Best / Worst Cases
: n a power of two (1 round).
: one round per set bit.
= : n = 2^{31} - 1 (31 rounds).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
When I look at this problem statement, the trigger phrase is "number of '1' bits" (also known as Hamming Weight or Population Count / popcount). A loop over every bit position works, but the count only needs one step per set bit: Kernighan's Bit Trick, n & (n - 1). At scale the same count runs word by word over large bitmaps, where each sparse word finishes in a few rounds.
LeetCode gives , so n has at most 31 set bits and the loop runs at most 31 times. It stops as soon as n reaches 0.
If an API can pass a negative value (a signed 32-bit register holding unsigned data), mask it to 32 bits first: while n > 0 returns 0 at once for a negative number, and while n: never ends on a negative Python int. Edge cases: (1 round) and (31 rounds).