Number of 1 Bits LeetCode Solution: The n & (n-1) Loop

Number of 1 Bits (#191) is the complement to Power of Two (#231). Where Power of Two checks for exactly one set bit, this number of 1 bits leetcode problem asks you to count them all. The result is called the Hamming weight — the total number of 1-bits in the binary representation of a 32-bit unsigned integer.

This problem introduces the most important bit manipulation trick you will use repeatedly: n & (n-1) clears the lowest set bit. Loop until n becomes zero, counting each iteration, and you have your answer. The technique is faster than checking all 32 positions when most bits are zero.

In this walkthrough, you will understand both approaches to counting set bits, trace through a concrete binary example of the n & (n-1) popcount algorithm, and see how this same trick connects to Power of Two (#231) and Counting Bits (#338).

Given a 32-bit unsigned integer, return the number of 1-bits in its binary representation. For example, input 11 has binary representation 1011, which contains three 1-bits, so the answer is 3. Input 128 is 10000000 in binary — just one set bit, so the answer is 1.

The Hamming weight measures how far a binary number is from zero. It appears throughout computer science in error detection codes, cryptography, and population count instructions in modern CPUs. Intel chips even have a dedicated POPCNT instruction that computes this in a single cycle.

Number of 1 Bits (#191) and Reverse Bits (#190) are the twin bit manipulation Easys on LeetCode. Both require you to process a 32-bit integer bit by bit, and they both appear at companies like Nvidia and AMD where bit-level operations are part of daily work.

The straightforward approach is to check every bit position one at a time. AND the number with 1 to check if the rightmost bit is set. If n & 1 equals 1, increment your count. Then right-shift n by one position to move the next bit into the rightmost slot. Repeat 32 times.

This runs in O(32) = O(1) time because you always iterate exactly 32 times regardless of the input. It works correctly for any 32-bit unsigned integer and is easy to understand. The implementation mirrors the approach from Reverse Bits (#190) — both process the integer one bit at a time from right to left.

The downside is that you always do 32 iterations even for sparse inputs like n = 1, which has only a single set bit. For most interview purposes this is perfectly acceptable, but there is a faster approach that only iterates once per set bit.

The elegant approach uses the n & (n-1) trick. Each time you compute n = n & (n-1), it clears the lowest set bit in n. Count how many times you can do this before n becomes zero, and that count is your Hamming weight. This is the popcount algorithm.

Why does n & (n-1) clear the lowest set bit? When you subtract 1 from n, all the bits below the lowest set bit flip, and the lowest set bit itself flips from 1 to 0. AND-ing n with this result zeros out everything at and below that position while preserving all higher bits. One set bit gone per iteration.

The time complexity is O(k) where k is the number of set bits. For sparse numbers like 1073741824 (which is 2^30, only one set bit), this does a single iteration instead of 32. For dense numbers like 4294967295 (all 32 bits set), it still does 32 iterations. On average, it is faster than checking every bit.

Let us trace the n & (n-1) approach for input n = 11, which is 1011 in binary. We expect the answer to be 3 because there are three 1-bits.

Iteration 1: n = 1011. Compute n - 1 = 1010. Compute n & (n-1) = 1011 & 1010 = 1010. The lowest set bit (position 0) has been cleared. Count = 1.

Iteration 2: n = 1010. Compute n - 1 = 1001. Compute n & (n-1) = 1010 & 1001 = 1000. The lowest remaining set bit (position 1) has been cleared. Count = 2.

Iteration 3: n = 1000. Compute n - 1 = 0111. Compute n & (n-1) = 1000 & 0111 = 0000. The last set bit (position 3) has been cleared and n is now 0. Count = 3. We are done — the Hamming weight is 3.

Notice that we only iterated 3 times, not 32. Each iteration cleared exactly one set bit and counted it. This is the power of the n & (n-1) trick for counting set bits: you skip over all the zero bits entirely.

The simplest edge case is n = 0, which has no set bits at all. The n & (n-1) loop never executes because n is already zero. The answer is 0, and both approaches handle this correctly without special casing.

The opposite extreme is n = 4294967295 (all 32 bits set). Every bit is 1, so the Hamming weight is 32. The n & (n-1) approach needs exactly 32 iterations here — one for each set bit — which matches the check-each-bit approach. This is the worst case for the popcount method.

A single set bit like n = 1 or n = 2147483648 (bit 31) should return 1. Alternating patterns like 0xAAAAAAAA (10101010... repeated) have exactly 16 set bits. These cases are useful for testing but do not require any special logic in your implementation.

Number of 1 Bits (#191) teaches you the single most reusable trick in bit manipulation: n & (n-1) clears the lowest set bit. This identical operation is what makes Power of Two (#231) a one-liner — a power of two has exactly one set bit, so n & (n-1) produces zero if and only if n is a power of two.

The problem is also the foundation for Counting Bits (#338), which asks you to compute the Hamming weight for every number from 0 to n. Once you understand the n & (n-1) relationship, you can derive the recurrence countBits[i] = countBits[i & (i-1)] + 1, which solves the entire problem in O(n) time with dynamic programming.

Practice this problem alongside Reverse Bits (#190), Power of Two (#231), and Counting Bits (#338) to build a complete toolkit for bit manipulation interviews. Review with YeetCode flashcards to make the n & (n-1) pattern automatic recall for interview day.