Why does n & (n - 1) clear the lowest set bit?

Subtracting 1 turns the lowest 1 bit of n into 0 and every 0 below it into 1, leaving the higher bits alone. ANDing with n keeps the higher bits and zeroes everything from that bit down, so exactly one 1 bit disappears.

Is this faster than checking every bit with n & 1?

Checking every bit always takes 32 rounds for a 32-bit integer. The n & (n - 1) loop takes one round per set bit, so it is faster when few bits are set. Both are O(1) for fixed-width integers.

What other problems use n & (n - 1)?

Power of Two (n > 0 and n & (n - 1) == 0) and Counting Bits, where bits[i] = bits[i & (i - 1)] + 1 builds the counts for every number up to n.

Number of 1 Bits

Count the set bits of an integer by clearing the lowest one with n & (n - 1) until nothing is left.

EasySolve on LeetCode

Problem Understanding

Number of 1 Bits: given a positive integer n, return how many 1s its binary form has (its Hamming weight).

Example: n = 11 is 1011 in binary, so the answer is 3.

Attempt 1: Check Every Bit

Test the last bit with n & 1, add it to the count, shift n right by one, and repeat until n is 0. That works, but it spends a round on every position up to the highest set bit, including all the zeros.

The Intuition: Jump Straight to the Next 1

Look at what subtracting 1 does in binary: the lowest 1 becomes 0, and every 0 below it becomes 1. Everything above stays the same.

n = 1 0 1 1 0 0
n - 1 = 1 0 1 0 1 1
n & (n - 1) = 1 0 1 0 0 0

So n & (n - 1) is n with its lowest 1 removed. Repeat until n is 0 and count the rounds: one round per 1 bit, and the zeros are skipped entirely.

Interactive Walkthrough

Three rows: n, n - 1 with the bits it flips filled in, and n & (n - 1). The lowest set bit of n is marked; in the result it is gone and nothing else has changed.

Dry Run Table

Input: n = 11

`n`	`n - 1`	`n & (n - 1)`	`count`
1011	1010	1010	1
1010	1001	1000	2
1000	0111	0000	3

Three rounds for three set bits: the answer is 3.

The Solution Template

Clear the lowest set bit until n is 0, counting the rounds.

Number of 1 Bits Code

1var hammingWeight = function(n) {
2    let count = 0;
3    while (n !== 0) {
4        n &= n - 1;
5        count++;
6    }
7    return count;
8};

Edge Cases & Common Mistakes

n = 0: the loop never runs; the answer is 0.
All 32 bits set: in Java, an int with the top bit set is negative; n != 0 still works because n & (n - 1) clears bits regardless of sign.
Using n > 0 as the loop condition in Java: a negative n would never enter the loop. Use n != 0.
Python integers: they are unbounded, so a negative input would loop forever; LeetCode's inputs are non-negative.

Summary

n & (n - 1) removes the lowest set bit. Repeating it until n is 0 counts the 1s in one round per set bit. The same identity tests powers of two and drives the Counting Bits DP.

More practice: DSA interview questions with answers · patterns cheat sheet

Single Number