Number of 1 Bits

Problem

Processors expose a popcount instruction used in compression codecs, error detection, and hardware diagnostics to count active flags in a bitmask. Given a non-negative integer n, return the number of 1-bits in its binary representation (also called the Hamming weight).

Input: n = 11    (binary: 1011)     → 3
Input: n = 128   (binary: 10000000) → 1
Input: n = 0     → 0

Solution

Approach - Brian Kernighan's lowest-set-bit strip.

The key operation is n &= n - 1, which clears exactly the lowest set bit of n and nothing else. Subtracting 1 borrows through the trailing zeros: it flips the lowest 1-bit to 0 and turns every bit below it into 1. ANDing that with the original n cancels precisely those changed positions - the lowest set bit and the run of zeros beneath it - while leaving all higher bits intact. Loop this while n is non-zero, counting one increment per iteration, and each pass removes one set bit. The loop therefore runs exactly popcount(n) times and returns the count.

This beats the naive shift approach (add n & 1, then n >>= 1) which always runs once per bit position - 32 times for a 32-bit integer - regardless of how many bits are actually set. Kernighan does work proportional to the number of 1s, so a sparse value finishes far sooner. Trace n = 11 = 1011: first 11 & 10 = 1010 (count 1), then 1010 & 1001 = 1000 (count 2), then 1000 & 0111 = 0000 (count 3), and the loop exits. Three iterations for three set bits, versus four shifts the naive method would need to clear the high bit.

Edge cases - n = 0 enters the loop zero times and returns 0 immediately. The same n & (n - 1) move doubles as the power-of-two test, where a single-strip result of 0 confirms exactly one bit was set.

Complexity - O(k) time where k is the number of set bits (at most O(log n)), O(1) space - only a counter and the mutating integer.