latency.lab
Algorithms · Topic 16

Bit Manipulation

Level: foundationTool: XOR cancellation, bit-clearing, and safe shiftingTime: ~75 min

By the end you can

Bit manipulation problems trade a data structure or a recurrence for a handful of primitive operations — XOR, AND, shifts — applied directly to a number's binary representation. The payoff is usually O(1) or O(32) time and O(1) space where a hash set or a DP table would otherwise be the first instinct. The cost is that C++'s integer types have real, easy-to-trip rules about what's well-defined and what's undefined behavior — this topic is as much about writing bit tricks *safely* as it is about knowing the tricks themselves.

XOR cancellation: pairs vanish, singles don't

Single Number is the cleanest example: XOR every element together, and every value that appears exactly twice cancels itself out (a ^ a == 0), leaving only the one value with no partner. Missing Number reuses the exact same cancellation, just XORing in the full expected index range alongside the actual values so everything genuinely present pairs off, leaving the one index that was never matched.

The habit to build

XOR cancellation only works when something appears an even number of times (usually exactly twice). The moment a problem says "three times" instead of "twice," the plain XOR-everything trick breaks — Single Number II's own quiz question walks through exactly why a ^ a ^ a is not 0.

0
0
0
1
= 1
0
0
0
1
= 1
0
0
1
0
= 2
0
0
1
0
= 2 (XOR of all three)
Single Number on [1, 1, 2], one bit column at a time. The two 1's are bit-for-bit identical, so they cancel to 0 in EVERY column (not just the ones where a difference happens to show) — what's left over is exactly 2's own bit pattern, untouched.

When XOR alone isn't enough: counting bits per position

Single Number II needs a different technique entirely: instead of XORing every number together, count how many numbers have a 1 at each of the 32 bit positions, independently. If everything but one value appears exactly three times, every bit position's count is a multiple of 3 — except at positions where the unique value has a 1, where the count is one more than a multiple of 3. Checking each position's count modulo 3 reconstructs the answer one bit at a time — a generalization of "pairs cancel" to "triples cancel."

Clearing the lowest set bit: n & (n - 1)

Number of 1 Bits and Hamming Distance both lean on the same single trick: n & (n - 1) clears exactly the lowest set bit of n. Repeating it until n reaches 0 counts the set bits in as many steps as there are set bits — never worse than 32, often far fewer. Counting Bits goes one step further and avoids repeating that work across many values: dp[i] = dp[i >> 1] + (i & 1) reuses the already-computed popcount of a smaller, related value instead of recounting from scratch.

Shifting to align, shrink, or search a range

Reverse Bits shifts one bit at a time to build a mirrored result. Bitwise AND of Numbers Range shifts both ends of a range down in lockstep until they're equal, exploiting the fact that any bit position where they still differ is guaranteed to be zeroed out somewhere in between. Divide Two Integers shifts a divisor up by decreasing powers of two to find how many times it fits into a dividend — turning what looks like repeated subtraction (potentially billions of steps) into a fixed 32 steps. Gray Code uses a single shift-and-XOR formula (i ^ (i >> 1)) to generate an entire sequence directly, with no search at all.

Safety: unsigned types are what make this well-defined

Sum of Two Integers is the clearest lesson in this topic on correctness, not just cleverness: computing a carry via AND-and-shift-left on a signed int risks shifting a 1 into (or past) the sign bit, which is undefined behavior the instant a carry actually needs it. Doing the same arithmetic in unsigned int sidesteps the problem entirely — unsigned overflow wraps, by the standard's own definition, exactly matching how two's-complement addition behaves in real hardware. The same habit shows up in Bitwise AND of Numbers Range and Single Number II: work in an unsigned (or wider) type internally, and only convert back to a signed result at the very end.

Common mistakes

  • Assuming XOR cancellation generalizes past pairs — it's specific to values appearing an even number of times; "appears three times" needs bit-counting-per-position instead.
  • Left-shifting a signed int until it overflows the sign bit — this is undefined behavior, not just a "wraps weirdly" surprise; do carry/overflow-prone shifting in an unsigned type instead.
  • Forgetting the one genuine overflow case in Divide Two Integers — INT_MIN / -1 is the single input whose true mathematical result doesn't fit in a 32-bit signed int, and needs an explicit clamp to INT_MAX.
  • Reaching for repeated subtraction or repeated doubling one step at a time — when a problem's true cost scales with the *magnitude* of the numbers rather than their *bit width*, that's the signal a bit-shift-based approach (testing powers of two, or shifting both ends of a range together) will be dramatically faster.

Takeaways

  • XOR cancels pairs; counting bits per position generalizes the same idea to values appearing three (or more) times.
  • n & (n - 1) clears the lowest set bit — the basis for both counting set bits and reusing that count across related values.
  • Shifting can align two numbers, shrink a range down to a shared prefix, or search across magnitudes in a fixed number of steps instead of one unit at a time.
  • Prefer unsigned (or wider) types for carry-prone or shift-heavy arithmetic — it turns undefined behavior into well-defined, correct wraparound.

Try it: XOR cancellation

Single Number — the simplest possible demonstration of pairs canceling under XOR.

Live

Loading starter code…

Try it: when XOR alone breaks

Single Number II — work through the "plain XOR gives 7, not 5" test case by hand before checking the hint.

Live

Loading starter code…

Try it: safe carry arithmetic

Sum of Two Integers — the clearest example in this topic of why unsigned types matter, not just as a style preference.

Live

Loading starter code…

Keep going

That's 3 of the 12 problems in this topic. Divide Two Integers is worth doing next — it combines the shifting ideas from this lesson with the same overflow-safety discipline as Sum of Two Integers. See the full Bit Manipulation set →

Checkpoint · Bit Manipulation

5 questions · pass at 70%

Q01
Single Number's XOR-everything trick correctly finds the one value that appears once when every other value appears exactly TWICE. Why does the same trick give a wrong answer when every other value appears exactly THREE times instead (Single Number II's setup)?
WhyXOR cancellation depends specifically on a ^ a == 0, which is what makes exactly two copies of a value vanish. Three copies don't cancel the same way -- a ^ a ^ a simplifies to a, not 0 -- so plain XOR-of-everything leaves behind extra, unwanted copies of values that were supposed to disappear, corrupting the result. That's why Single Number II needs an entirely different technique: counting set bits per position and checking each count modulo 3.
Q02
Sum of Two Integers computes a carry using (a & b) << 1, and does this arithmetic in unsigned int rather than int. Why does the choice of unsigned vs signed actually matter here?
WhyLeft-shifting a signed int in a way that shifts a 1 into or past the sign bit is undefined behavior in C++ -- not just 'implementation-defined' or 'wraps weirdly,' but a genuine correctness hazard a sanitizer will flag. The exact same shift on an unsigned int is well-defined: unsigned arithmetic wraps modulo 2^32 by the language's own rules, which happens to be exactly the two's-complement wraparound that real addition hardware performs. Doing the carry/XOR arithmetic in unsigned int gets the correct wrapped answer with no undefined behavior at all.
Q03
Divide Two Integers has exactly ONE input pair that requires clamping the result to INT_MAX rather than returning the true mathematical answer. What is that input, and why is it the only one?
WhyINT_MIN's magnitude is 2^31, one more than INT_MAX's 2^31 - 1. Dividing INT_MIN by -1 would mathematically produce positive 2^31, which is exactly one past the largest value a 32-bit signed integer can hold -- the only division result in the entire valid input space that genuinely doesn't fit. Every other combination, including INT_MIN divided by 1 (which stays INT_MIN, already representable) or INT_MIN divided by itself (which is 1), fits without needing any clamping.
Q04
Bitwise AND of Numbers Range finds the shared bit prefix of left and right by shifting both down together until they're equal, then shifting the result back up. Why is repeatedly ANDing every single number in the range, one at a time, a poor approach for large ranges?
WhyThe magnitude of the range (right - left) can be enormous -- up to roughly 2^31 for the widest valid ranges -- so looping through every single value in it is not remotely practical. The shift-based technique instead operates on the BIT WIDTH of the numbers, not their magnitude: at most 32 shifts are ever needed to find the shared prefix, regardless of how far apart left and right actually are.
Q05
Counting Bits computes dp[i] = dp[i >> 1] + (i & 1) instead of recomputing each value's set-bit count from scratch with the n & (n-1) trick. What does this recurrence actually reuse, and why does it save work?
Whyi >> 1 is exactly i with its lowest bit removed, and since that's a smaller index processed earlier in the same left-to-right pass, its popcount (dp[i >> 1]) is already sitting in the table. Adding i & 1 accounts for the one bit that got dropped by the shift. This turns an O(32) recount per value (O(32n) total) into a single O(1) table lookup and addition per value (O(n) total) -- reusing already-computed work instead of repeating it.

Finished Bit Manipulation?

Pass the quiz to complete it automatically.