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).

Example 1:

Input: n = 13    (binary: 1101)
Output: 3

Example 2:

Input: n = 64   (binary: 1000000)
Output: 1

Example 3:

Input: n = 0
Output: 0

Constraints:

• 0 <= n <= 2^31 - 1

Solution Breakdown

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 = 13 = 1101: first 13 & 12 = 1100 (count 1), then 1100 & 1011 = 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.