Bit Tricks
What is this?
Apply a bitwise operator to a whole collection and it destroys information on purpose, and what survives is the answer. XOR annihilates everything that appears in pairs, so an unpaired value is left standing alone. AND annihilates every bit that ever changes, so only the bits shared by everything remain.
Both turn a counting problem into a single accumulator and one pass. The habit worth taking away is asking what the operator destroys, rather than what it computes.
Fun fact: Bitwise AND of Numbers Range looks like it needs to iterate from
lefttoright, which for a range of a billion numbers is hopeless. But if the endpoints differ at some bit position, then every bit from that position down must flip somewhere inside the range, so all of them are annihilated. What remains is exactly the common binary prefix of the two endpoints, found by shifting both right until they agree and shifting back. A CIDR block such as10.0.0.0/24is also "addresses sharing a common prefix", which is why the two ideas feel related.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
In short: fold a whole collection with one operator and read what survives. XOR leaves the unpaired value, AND over a range leaves the shared prefix.
1. XOR cancels pairs
x ^ x = 0 and x ^ 0 = x, and XOR is commutative and associative, so a collection can be folded in any order and every value appearing an even number of times vanishes. When the problem guarantees "everything is paired except one", folding is the algorithm:
def find_the_difference(s, t):
result = 0
for ch in s:
result ^= ord(ch) # matched characters cancel
for ch in t:
result ^= ord(ch)
return chr(result)
O(n) time, O(1) space, no frequency map (two loops rather than s + t, which would copy both strings). It works on characters because they fold through their code points, and it works in any order because XOR does not care about sequence.
2. AND collapses a range to its prefix
def range_bitwise_and(left, right):
shift = 0
while left != right: # strip differing low bits
left >>= 1
right >>= 1
shift += 1
return left << shift # restore the shared prefix
The loop runs at most 31 times for non-negative 32-bit inputs, regardless of how wide the range is. The argument for correctness: if left and right first differ at bit i, the range contains a number with a 1 at bit i and zeros below it, and the number just before it, which has a 0 at bit i and ones below. So every bit from i down is 0 somewhere in the range and cannot survive the AND.
3. A 30-second worked example
Bits 0 and 1 both flip somewhere inside [5, 7] and are annihilated; bit 2 is set in all three numbers and survives. Two shifts replaced iterating the range.
4. Where you'll actually meet this
- Address prefixes. A subnet like
10.0.0.0/24is the set of addresses sharing a high-order prefix, the same structure range-AND exposes. Compiling arbitrary ranges into prefix rules is a related but harder problem. - Parity and checksums. XOR is the fold behind simple parity bytes, and RAID-5 parity is the XOR of the data blocks, so a lost block is the XOR of the rest.
- Reconciliation. Two sides should hold the same multiset and you need the single discrepancy, in constant space.
- Flag masks. AND over a set of masks gives the capabilities common to all of them.
5. Problems in this chapter
Find the Difference
t is s shuffled with one extra character inserted. XOR every character of both; matched characters cancel and the survivor is the addition.
Pattern: XOR cancellation. Target: O(n) time, O(1) space (a count map is O(k) for alphabet size k).
Bitwise AND of Numbers Range
AND every integer in [left, right]. Shift both endpoints right until they agree, then shift the shared prefix back.
Pattern: common-prefix collapse. Target: O(log n) time, O(1) space.
Set Mismatch
One number in 1..n is duplicated and one is missing. XOR the array against 1..n to get dup ^ missing, split everything on a set bit of that result so each anomaly is alone in its bucket, then check which of the two is present in the array.
Pattern: XOR fold plus bit partition. Target: O(n) time, O(1) space (counting is O(n) space, index marking needs to mutate the input).
6. Common pitfalls
- Iterating
lefttoright. With a range of a billion this never finishes; the endpoints are all you need. - Reaching for a frequency map in the XOR problem. It is correct, but it allocates a map and misses the point.
- Summing character codes instead of XOR-ing. It works here, but sums can overflow in fixed-width languages where XOR never does.
- Forgetting
left == right. The loop must handle a single-element range, where the answer is the value itself. - Assuming XOR finds any duplicate. It only isolates a value appearing an odd number of times among otherwise-paired ones.
- Using signed shifts carelessly in languages where
>>propagates the sign bit. - Skipping the presence check in Set Mismatch. The two buckets give you the duplicate and the missing number unlabeled; the duplicate is the one that appears in the array.
7. Key takeaways
- Ask what the operator destroys. The survivors are the answer.
x ^ x = 0is the whole XOR trick, and order never matters.- A flipping bit cannot survive an AND, so only the shared prefix remains.
- Never loop a numeric range when the endpoints determine the result.
- Characters fold through their code points, so XOR works beyond integers.
- Constant space is the real prize. These are the techniques for when a map is unaffordable. Set Mismatch shows the limit: with two anomalies, one XOR fold is not enough and you need the bit partition.
- Why interviewers like it: the brute force is obvious and the insight is small but genuine, which makes them efficient screening questions.
Order: Find the Difference → Bitwise AND of Numbers Range → Set Mismatch.
Core idea: Strings
sandthold the same characters exceptthas one extra. XOR every character of both strings together. Every matched pair cancels itself out (a ^ a = 0), and the lone survivor is exactly the added character.
Problem, rephrased
You run a packet-relay service: a client sends a batch of characters, and the relay forwards it, but a buggy middlebox shuffles the batch in transit and slips in exactly one extra character. You're given the two strings s and t: s is the batch the client sent, and t is what arrived: s shuffled, with one added character inserted at a random position.
Return the character that was added. The shuffle destroys all position information, and the extra character may duplicate one already present in s, so the question is which character has one more occurrence in t than in s, not which symbol is new.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson