Number of 1 Bits
Number of 1 Bits: count the set bits in an unsigned integer using n & (n-1) to strip the lowest one each round.
- 1 <= n <= 2³¹ - 1
Intuition
Number of 1 bits counts the set bits in an integer, also called the Hamming weight. Several methods exist, and they differ in how much work they do per bit.
The straightforward loop shifts the number right one position at a time, testing the lowest bit with n & 1. It runs a fixed 32 iterations regardless of how many bits are actually set.
Brian Kernighan's method does better by skipping the zeros entirely:
- n & (n − 1) clears the lowest set bit, so looping until n reaches zero runs once per set bit rather than once per bit position.
The reason it works is that subtracting 1 flips the lowest set bit to 0 and turns every zero below it into 1. The AND then keeps only the bits above, discarding exactly one set bit per iteration.
On a number with three set bits, that is three iterations rather than 32.
In languages with signed 32-bit integers, the naive right-shift loop must use an unsigned shift. An arithmetic shift on a negative number fills with 1s from the left and the loop never terminates — a hazard Kernighan's method avoids entirely, since it converges to zero regardless of sign.
Built-ins exist too — Integer.bitCount in Java, bin(n).count('1') in Python — and are the right choice unless the problem forbids them.
The stated follow-up asks about calling the function many times, where a lookup table of precomputed counts for each byte answers in four array reads.
All variants are O(1) for fixed-width integers, differing only in constant factors.
n &= n - 1 clears the lowest set bit, so the loop runs once per set bit rather than once per bit position. Brian Kernighan's algorithm — the same identity behind the power-of-two test, used here to count instead of to check.
Approach
Before reading on: price up what the direct approach costs here, then ask which operator makes the unwanted values cancel themselves out. Aim for O(k) where k is the number of set bits (at most 32) time and O(1) space.
Start with the shift loop
Test the lowest bit with n & 1 and shift right, 32 times. Correct but does full work regardless of how many bits are set.
Use Kernighan's method
n & (n - 1) clears the lowest set bit, so the loop runs once per set bit. Three set bits means three iterations, not 32.
Understand why it works
Subtracting 1 flips the lowest set bit to 0 and sets every zero below it. The AND keeps only the higher bits, removing exactly one set bit per step.
Beware the signed shift
In signed languages, use an unsigned right shift. An arithmetic shift on a negative number fills with 1s and the loop never terminates — Kernighan's method sidesteps this.
Prefer the built-in when allowed
Integer.bitCount or bin(n).count('1') is clearest and usually fastest, unless the problem explicitly forbids library calls.
Answer the follow-up with a table
For many repeated calls, precompute counts for each byte and sum four lookups. This trades 256 entries of memory for constant-time answers.
Cost of the approaches
All are O(1) for fixed-width integers — at most 32 iterations — differing only in constant factors. Space is O(1), or O(256) with the lookup table.
Solution & live demo
Common pitfalls
Iterating all 32 positions
for i in range(32):
count += (n >> i) & 1while n:
n &= (n - 1)
count += 1Correct but always 32 iterations regardless of input. Clearing the lowest set bit runs exactly as many times as there are 1s — often far fewer, and never more.
Using a signed right shift in Java
while (n != 0) { count += n & 1; n >>= 1; }while (n != 0) { n &= (n - 1); count++; }Java's >> propagates the sign bit, so a negative input shifts in 1s forever. The n & (n-1) form has no shift at all and terminates for every input.
Converting to a binary string
return bin(n).count('1')n &= (n - 1)
Fine in Python for positives, but it allocates a string and gives the wrong answer for negative values, whose binary representation includes a minus sign rather than a two's-complement pattern.
Edge cases
Loop body never executes; count stays 0.
Only one set bit, so the loop runs exactly once regardless of n's magnitude.
Loop runs 32 times, once per bit, still far cheaper than testing every position when bits are sparse in general.
Use an unsigned shift or mask (e.g. n & 0xFFFFFFFF) so the sign bit does not cause infinite loops or negative comparisons.