The Quest Begins (The "Why")
I still remember the first time I stared at a problem that asked me to count the number of 1 bits in a 32‑bit integer. My first instinct? Loop from 0 to 31, shift the number right each time, and add (n & 1). It worked, but it felt like I was brute‑forcing a locked door with a sledgehammer. Every test case ran fine, yet something nagged at me: why am I checking bits that are definitely zero?
If you’ve ever solved a problem on LeetCode, Codeforces, or at a whiteboard interview, you’ve probably felt that same irritation. You know there’s a smarter way, but the trick feels like a secret spell whispered only by the competitive‑programming elders. I spent a weekend digging through old tutorial posts, and when the penny finally dropped, I felt like I’d just discovered a hidden shortcut in a maze—the kind of moment that makes you want to jump out of your chair and shout “Yes!”
The Revelation (The Insight)
The magic trick is this: n & (n‑1) clears the lowest set bit of n.
Let’s unpack why that’s true, because understanding the why makes the technique stick forever.
Take any positive integer n. In binary, it looks like a string of bits ending with a 1 (the lowest set bit) followed by zero or more 0s. For example, n = 1011000₂ (the lowest set bit is the third from the right).
Now compute n‑1. Subtracting one flips that lowest 1 to 0 and turns all the trailing 0s into 1s. So n‑1 for our example becomes 1010111₂.
When we AND the two numbers together, every bit that was 1 in both survives; every bit that differs becomes 0. The lowest set bit of n is 0 in n‑1, so it disappears. All higher bits are identical in n and n‑1, so they stay unchanged. The trailing bits that were 0 in n become 1 in n‑1, but AND‑ing 0 with 1 still yields 0. The result? Exactly the same as n but with that lowest 1 wiped out.
In code:
int cleared = n & (n - 1); // lowest 1-bit gone
Why does this matter for counting bits? Because each time we apply n & (n‑1), we remove one 1. If we repeat the operation until n becomes zero, the number of iterations equals the number of set bits. No wasted walks over zero bits—just a tight loop that runs O(k) where k is the popcount (the number of 1s).
That’s the insight: a single bit‑wise trick turns a linear‑scan over a fixed word size into a loop whose length depends only on the actual data.
Wielding the Power (Code & Examples)
Before: the naïve approach
int hammingWeightNaive(uint32_t n) {
int cnt = 0;
for (int i = 0; i < 32; ++i) { // always 32 steps
if (n & (1 << i)) cnt++;
}
return cnt;
}
It’s simple, but it does the same work whether n is 0 or 0xFFFFFFFF.
After: Brian Kernighan’s method (the cleared‑bit trick)
int hammingWeight(uint32_t n) {
int cnt = 0;
while (n) { // runs only as many times as there are 1‑bits
n &= n - 1; // clear lowest set bit
++cnt;
}
return cnt;
}
Why it’s O(k): each iteration removes one 1. If the number has k ones, we loop k times; if it’s zero, we skip the loop entirely.
Common trap
A frequent mistake is to write n = n & (n-1); inside a for loop that also increments a counter based on n’s original value, like:
int bad(uint32_t n) {
int cnt = 0;
for (int i = 0; i < 32; ++i) { // <-- still hard‑coded 32!
n &= n - 1;
if (n) cnt++; // off‑by‑one error
}
return cnt;
}
The loop still runs 32 times, and the if (n) guard can miss the last cleared bit. The fix is to let the loop condition itself be while (n).
Real interview problems
1. Number of 1 Bits (LeetCode 191)
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).
Using the trick above gives a clean, fast solution that interviewers love because it shows you know bit‑level optimizations.
2. Power of Two Check
Given an integer
n, return true if it is a power of two.
A number is a power of two iff it has exactly one set bit. So we can reuse the same idea:
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0; // clears the only 1‑bit → zero
}
If n had more than one 1, n & (n-1) would leave at least one bit set, yielding a non‑zero result.
Both problems run in O(k) time, where k is the number of set bits (at most 32 for a 32‑bit int), and O(1) space.
Why This New Power Matters
Mastering n & (n‑1) does more than let you ace a couple of LeetCode questions—it reshapes how you think about integers. Suddenly, you see binary not as a static string of 0s and 1s but as a mutable resource you can chip away at, one meaningful bit at a time.
In contests, this trick shaves off precious milliseconds when you need to process millions of numbers (think of counting bits in a large array or solving subset‑sum‑style DP with bitmask tricks). In interviews, it signals that you’re not just memorizing patterns; you understand the underlying arithmetic and can derive solutions on the spot.
And honestly, there’s a certain joy in watching a number shrink to zero with each n &= n‑1—it’s like watching a boss lose health points in a game, each hit taking away exactly one life bar until the victory fanfare plays.
Your Turn
Grab a piece of paper (or an IDE) and try this:
- Write a function that returns the index (0‑based) of the least significant set bit using only
n & (n‑1)and a counter. - Extend it to return the position of the most significant set bit without converting to a string.
Drop your solution in the comments, or tweet it with #BitwiseAwakening. I can’t wait to see how you wield this newfound power!
May your bits always be set just right. 🚀
