Number of 1 Bits LeetCode 191 Deep Dive

LeetCode 191 — Number of 1 Bits — gives you an unsigned integer and asks you to return the number of 1 bits in its binary representation. This count is formally called the Hamming weight or popcount. For example, the integer 11 is 1011 in binary and has three 1 bits, so the answer is 3. The integer 128 is 10000000 and has one 1 bit, so the answer is 1. The integer 4294967293 (0xFFFFFFFD) has thirty-one 1 bits.

The problem is rated Easy, but it is a gateway to a broad family of bit manipulation techniques. Interviewers use it to probe whether you can work directly with binary representations, understand the difference between logical and arithmetic right shifts, and apply non-obvious bitwise identities like n & (n-1). A complete answer covers at least two approaches and explains the trade-offs.

The constraints specify that n is treated as an unsigned 32-bit integer. In Python this is natural since integers are arbitrary-precision, but in Java and C++ you must be careful with the right shift operator. The follow-up asks: if this function is called many times, how would you optimize? The answer involves precomputing a lookup table for 8-bit or 16-bit chunks and stitching together the results.

The straightforward approach checks each of the 32 bits one at a time. Use the expression n & 1 to isolate the least significant bit: if the result is 1, that bit is set and you increment the count. Then right-shift n by one position (n >>= 1 in Java using unsigned shift, n >>= 1 in Python) to move the next bit into the least significant position. Repeat exactly 32 times to cover all bits of a 32-bit integer.

This approach runs in O(32) = O(1) time and O(1) space regardless of the input. It is simple to implement and trivial to verify: the loop always runs exactly 32 times, the bit check is a two-line operation, and the result accumulates in a single counter variable. For an interview warm-up or a competitive programming submission, this is perfectly acceptable.

The main drawback is that the loop always runs 32 iterations even if n has only one or two 1 bits. For an integer like 1 (binary: 00000000 00000000 00000000 00000001), the loop processes 31 zero bits and one 1 bit. Brian Kernighan's trick eliminates wasted work by jumping directly from one set bit to the next.

Brian Kernighan's bit-counting trick exploits the identity n & (n-1) to clear the lowest set bit of n in a single operation. The algorithm is: initialize count to 0; while n is not zero, execute n = n & (n-1) and increment count; return count. Each iteration removes exactly one 1 bit from n, so the loop runs exactly k times where k is the number of 1 bits — the Hamming weight itself.

This approach is O(k) time where k is the number of 1 bits, which is always less than or equal to 32 for a 32-bit integer. For dense integers (many 1 bits), it performs similarly to the loop-and-check approach. For sparse integers (few 1 bits), it is dramatically faster — an integer with a single 1 bit takes exactly one iteration rather than up to 32. The space complexity is O(1).

The trick was popularized by Brian Kernighan and is documented in the book 'The C Programming Language.' It appears throughout competitive programming and systems code wherever popcount operations are needed without hardware support. Understanding why n & (n-1) works — not just that it works — is what interviewers expect.

To understand why n & (n-1) clears exactly the lowest set bit, consider what subtracting 1 does in binary. If the lowest set bit of n is at position p, then n ends with a 1 at position p followed by zeros below it. Subtracting 1 flips the bit at position p from 1 to 0, and fills all the zero positions below p with 1s. All bits above position p remain unchanged.

When you AND n with (n-1), the bits above position p are the same in both, so they survive the AND unchanged. The bit at position p is 1 in n and 0 in (n-1), so the AND produces 0 at position p — clearing it. The bits below position p are 0 in n and 1 in (n-1), so the AND produces 0 — they stay zero. The net result: exactly the lowest set bit is cleared, and nothing else changes.

Example: n = 12, binary 1100. n-1 = 11, binary 1011. n & (n-1) = 1100 & 1011 = 1000 = 8. The lowest set bit was at position 2 (value 4), and it has been cleared. Another iteration: n = 8, binary 1000. n-1 = 7, binary 0111. n & (n-1) = 1000 & 0111 = 0000. The loop terminates after 2 iterations — correctly reporting that 12 has two 1 bits.

Most production languages provide a built-in popcount function backed by a hardware POPCNT instruction where available. In Python, bin(n).count('1') converts n to its binary string representation and counts the '1' characters — simple and correct but not the fastest. Python also provides int.bit_count() in Python 3.10+, which uses the hardware instruction directly.

In Java, Integer.bitCount(n) returns the number of 1 bits in a 32-bit integer. It is implemented using a sequence of bit-twiddling operations that compute the popcount in parallel across groups of bits — effectively summing pairs, then groups of four, then groups of eight, and so on. In C++, __builtin_popcount(n) calls the compiler intrinsic which maps to the POPCNT instruction on x86 processors with SSE4.2 support.

Using built-in functions is appropriate in competitive programming where correctness and speed matter more than demonstrating understanding. In a technical interview, however, the interviewer almost always expects you to implement the bit counting manually. Mention the built-in as an alternative, implement Brian Kernighan's trick as your primary answer, and explain why the manual implementation is preferred for demonstrating algorithmic knowledge.

Python — loop and check: def hammingWeight(n): count = 0; [code] for _ in range(32): count += n & 1; n >>= 1; return count. Python — Brian Kernighan: def hammingWeight(n): count = 0; while n: n &= n - 1; count += 1; return count. Python — one-liner: def hammingWeight(n): return bin(n).count('1'). All three are O(1) time and O(1) space. Brian Kernighan is the interview favorite for demonstrating bit manipulation depth.

Java — loop and check with unsigned right shift: public int hammingWeight(int n) { int count = 0; for (int i = 0; i < 32; i++) { count += n & 1; n >>>= 1; } return count; }. Java — Brian Kernighan: public int hammingWeight(int n) { int count = 0; while (n != 0) { n &= n - 1; count++; } return count; }. Java — built-in: return Integer.bitCount(n). The Brian Kernighan version avoids the signed/unsigned right shift issue entirely because it does not use right shift at all.

All three approaches share O(1) time and O(1) space complexity for 32-bit inputs. The loop-and-check approach always runs exactly 32 iterations. Brian Kernighan runs k iterations where k is the Hamming weight — optimal. Built-ins run in a single instruction on modern hardware. In an interview, lead with Brian Kernighan, explain the n & (n-1) identity, mention the Java unsigned right shift caveat for the loop approach, and note the built-in as a competitive programming shortcut.

Reverse Bits (LeetCode 190) is the natural companion to Number of 1 Bits — both operate on 32-bit unsigned integers bit by bit. Reverse Bits extracts the least significant bit and builds the reversed result by left-shifting the accumulator and ORing in each extracted bit. The loop runs exactly 32 times, and the same unsigned right shift caveat applies in Java. Mastering LeetCode 191 makes LeetCode 190 straightforward.

Counting Bits (LeetCode 338) generalizes the problem: given n, return an array where result[i] is the number of 1 bits in i, for all i from 0 to n. The brute force applies hammingWeight to each number for O(n log n) total, but the optimal dynamic programming solution uses the identity result[i] = result[i >> 1] + (i & 1) to fill the table in O(n). This is a direct extension of the bit-counting concepts from LeetCode 191.

Single Number (LeetCode 136) uses XOR rather than popcount: XOR of a number with itself is 0, and XOR is associative and commutative, so XOR-ing all elements of an array where every element appears twice except one leaves the unique element. The bit manipulation family — Number of 1 Bits, Reverse Bits, Counting Bits, Single Number, and Power of Two — represents the core bit manipulation curriculum that appears repeatedly in FAANG interviews.