3.7.20 · D5Algorithm Paradigms
Question bank — Bit manipulation — XOR tricks, LSB, counting set bits
A quick vocabulary refresher so no symbol here is unearned:
True or false — justify
Never answer bare "true/false" — the reasoning is the whole point.
for every integer , including negatives.
True. XOR compares bits position-by-position; every bit equals itself, so no position "differs," so every output bit is . Sign/two's-complement storage does not change this — it works bit-for-bit regardless of what the number means.
.
False. That confuses two laws. XOR with is the identity: (nothing differs from except where already had a ). It is that gives .
XOR is associative, so can be grouped and reordered freely.
True. Each bit position is computed independently, and single-bit XOR is just addition mod , which is associative and commutative. So the whole-word XOR inherits both — this is why XOR-ing a list in any order still cancels pairs.
x & -x returns the highest set bit of x.
False — it returns the lowest set bit. Two's complement builds so its bits above the lowest set position are the complement of 's (they cancel to under AND), while the lowest set bit and its trailing zeros stay aligned and survive.
For any non-zero x, x & (x-1) has exactly one fewer set bit than x.
True. Subtracting flips the lowest set bit to and turns the zeros below it into ones; ANDing with clears that whole low block, removing precisely one set bit and leaving all higher bits intact.
x & (x-1) == 0 means x is a power of two.
Mostly true, one exception. It means has at most one set bit — true for every power of two, but also for . A safe power-of-two test is
x != 0 && (x & (x-1)) == 0.XOR-ing the whole array finds the unique element as long as it is the only odd-count value.
True, with a hidden condition. All other values must appear an even number of times so they cancel to . If any other value also appears an odd number of times, its bits survive too and corrupt the answer.
Left shift x << k always equals exactly.
False in fixed-width reality. Mathematically yes, but in a finite-width integer the top bits can shift off the end (overflow), so the stored result may not equal . It's exact only while no set bit is pushed past the highest position.
x >> 1 equals for every integer.
False for negatives with arithmetic shift. For unsigned/non-negative it's . For negative , arithmetic right shift rounds toward , e.g. , whereas integer division toward gives .
The Brian Kernighan popcount loop runs once per bit of the word (e.g. 32 times).
False. It runs once per set bit, because each iteration clears exactly one set bit via
x &= x-1. For a sparse number like it loops only once, not times.Spot the error
Each line has a bug or a wrong claim. Say what breaks and why.
"To swap two array slots I always do a[i]^=a[j]; a[j]^=a[i]; a[i]^=a[j];."
Breaks when
i == j (the two slots alias). The first line does a[i]^=a[i], zeroing it, and the value is lost forever — both end up . The temp-variable swap has no such trap."x & -x isolates the lowest set bit, so it works fine for x = 0 too, giving the lowest bit."
For there is no set bit; , so
0 & 0 = 0. The formula returns , meaning "no lowest set bit," which you must handle as a special case rather than assume a bit exists."popcount naive loop: while x: count += x & 1; x <<= 1."
Wrong shift direction. Shifting left never removes the LSB you just read and pushes bits away from position , so this loops forever (or until overflow). It must be
x >>= 1 to expose the next higher bit each step."Missing number: XOR just the array elements, then that's the answer."
You must also XOR in every index . Only when present values cancel against their matching indices does the single absent value remain. XOR-ing the array alone leaves an XOR of all present numbers, which is meaningless here.
"~x gives the highest bit, since NOT flips everything."
~x flips all bits, producing a completely different number (in two's complement, ), not "the highest bit." Isolating the highest set bit needs — see Logarithms and Powers of Two."Single-number trick also works for [a,a,a,b] (all thrice, one once)."
XOR only cancels even repetitions. Three copies of give , so does not vanish. The "one unique among triples" problem needs bit-by-bit counting mod , not plain XOR.
"Using a hash set and the XOR trick have the same space cost."
A hash set stores up to elements — extra memory. The XOR accumulator is a single integer — space. That memory saving is the entire reason XOR tricks exist.
Why questions
Explain the mechanism, not just the outcome.
Why does XOR cancel a duplicated value but keep a lone one?
Because : two copies annihilate to zero, and lets that zero pass through harmlessly. So any value appearing an even number of times self-destructs, and only odd-count values survive.
Why does two's complement make x & -x land on the lowest set bit specifically?
Adding to the flipped bits ripples through the trailing ones (which were the trailing zeros of ) and stops at the lowest original , leaving that bit and everything below it identical to while every higher bit becomes complemented — so AND keeps only that lowest bit.
Why is Brian Kernighan's popcount faster than the naive loop for sparse numbers?
The naive loop runs once per bit width regardless of content; Kernighan's runs once per set bit, clearing one each pass. A number with two s in a -bit word costs iterations, not .
Why can XOR swap be slower than using a temporary, despite looking clever?
It creates a data dependency chain (each line needs the previous result) that a CPU cannot parallelize, whereas a temp swap lets the processor move both values freely. Modern hardware makes the temp version at least as fast, plus it's alias-safe.
Why does the "single number" idea generalize to the missing-number problem?
Both rely on pairing. Present values pair with their equal indices and cancel; the missing number has an index with no matching value, so it stays. It's the same "odd one out" logic, just pairing array-vs-range instead of within one array.
Why must you use unsigned types for pure bit twiddling?
Signed right shifts fill with the sign bit and round toward , and signed overflow is often undefined behaviour. Unsigned types give the clean logical shifts and modular wraparound that bit tricks assume.
Edge cases
The scenarios that break naive intuition — never let the reader meet an unhandled input.
What does x & -x return when x = 0?
, because and . There is no lowest set bit, so callers must treat as a special "no bit" case.
Does the power-of-two test flag x = 1?
Yes, correctly. has one set bit;
1 & 0 == 0 and , so it passes — and genuinely is a power of two.Does x & (x-1) == 0 incorrectly flag x = 0 as a power of two?
Yes, if you forget the
x != 0 guard: 0 & -1 == 0 passes even though is not a power of two. Always pair the check with a non-zero test.What does the missing-number XOR return if the array is a complete with nothing missing?
. Every index cancels with its present value, leaving no survivor — and correctly signals "nothing absent" only if you frame the range so the true answer can't legitimately be ; otherwise it's ambiguous and needs care.
What is the popcount of the all-ones word, and does Kernighan's loop still terminate?
For a -bit all-ones value the popcount is , and the loop runs exactly times (its worst case) — one clear per set bit — then hits and it stops. No infinite loop.
What happens to x & -x on the most negative two's-complement integer (only the sign bit set)?
Its lowest — and only — set bit is the sign bit, so
x & -x returns that sign bit itself. Here overflows back to , yet the AND still isolates the single set bit correctly.If a value appears an even number of times but not exactly twice, does the single-number XOR still cancel it?
Yes. Only parity matters: four, six, or any even count XORs to . The "appears twice" phrasing is just the common case; the real requirement is even multiplicity.
Recall One-line self-test before moving on
Cover each and recite the reason: (1) why , (2) why x & -x is the low bit, (3) why the power-of-two test needs x != 0, (4) why Kernighan loops per set bit. If any reason is fuzzy, reread the parent note's derivations.
Connections
- Two's Complement Representation — the source of every
-xand~xsurprise above. - Hash Sets vs O(1)-space tricks — the memory contrast behind the XOR "why" questions.
- Bitmask Dynamic Programming — where these traps recur at subset scale.
- Logarithms and Powers of Two — highest-bit vs lowest-bit reasoning.
- Greedy and Divide-and-Conquer (Algorithm Paradigms)