Bit Tricks

What is this?

Apply a bitwise operator to a whole collection and it destroys information on purpose — and what survives the destruction 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 left to right, which for a range of a billion numbers is hopeless. But if the endpoints differ at some bit position, then every lower bit 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. It is the same computation a router performs to describe a contiguous block of IP addresses as one CIDR prefix.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

---

The one-line idea: 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 + t:
        result ^= ord(ch)        # matched characters cancel
    return chr(result)

O(n) time, O(1) space, no frequency map. 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 32 times regardless of how wide the range is. The argument for correctness: if left and right differ at some position, the range must cross a boundary where every bit below that position takes both values — so each 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

• Network routing. Range-AND is the CIDR prefix calculation, performed on every packet forwarding decision.
• Checksums and integrity. XOR parity detects single-bit errors in RAID and simple checksum schemes.
• Deduplication. Finding the one unpaired record in a stream, in constant space.
• Permission and flag masks. Determining which capabilities are common to an entire set of roles.
• Embedded systems. Constant-space, allocation-free algorithms where a hash map is not an option.

---

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.

▶ 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.

---

6. Common pitfalls 🚫

• Iterating left to right. With a range of a billion this never finishes; the endpoints are all you need.
• Reaching for a frequency map in the XOR problem. Correct, O(n) space, and it misses the point.
• Summing character codes instead of XOR-ing. It works here, and it overflows 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.
• Set Mismatch — one number is duplicated and one is missing. XOR every value with every index to fold both errors into a single number, then split them apart on any set bit of that result — or count, which is simpler to explain and just as fast.

---

7. Key takeaways

1. Ask what the operator destroys. The survivors are the answer.
2. x ^ x = 0 is the whole XOR trick, and order never matters.
3. A flipping bit cannot survive an AND — so only the shared prefix remains.
4. Never loop a numeric range when the endpoints determine the result.
5. Characters fold through their code points, so XOR works beyond integers.
6. Constant space is the real prize. These are the techniques for when a map is unaffordable.
7. 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.