Overview
This lecture focuses on the properties and practical applications of the XOR (exclusive OR) operation, demonstrating its use in swapping values, solving missing/duplicate number interview problems, and explaining its role in error correction.
XOR Basics and Properties
- XOR (exclusive OR) operation outputs 1 only when the two input bits are different.
- XOR is commutative (order doesn't matter) and associative (grouping doesn't matter).
- XOR with zero returns the original value: x ^ 0 = x.
- XOR with the same value cancels to zero: x ^ x = 0.
- XOR operates bitwise on numbers in most programming languages.
Swapping Values Using XOR
- Two variables can be swapped in place using three XOR operations:
- a = a ^ b
- b = a ^ b
- a = a ^ b
Finding a Missing Number in an Array
- Given n-1 integers in the range 1 to n, with one missing, XOR all numbers from 1 to n and all numbers in the array.
- Due to cancellation, only the missing number remains after XORing the two results.
- This works even if the array is unsorted.
Handling Duplicates and Error Correction
- The same XOR trick applies for finding a duplicate when all numbers from 1 to n are present with one duplicate.
- XOR is central to forward error correction (FEC) by allowing lost data recovery from XORed data packets.
- XOR can be used in data transmission to recover any single lost packet when the XOR of all packets is transmitted.
Finding Two Missing Numbers
- If two numbers are missing, XOR all numbers from 1 to n and the array to get uv = u ^ v (the XOR of the two missing numbers).
- Find the least significant bit where u and v differ.
- Partition numbers into two groups based on this bit; each group will have one missing number.
- Use the single-missing-number XOR method within each partition to identify both missing numbers.
Limitations of XOR
- The method breaks down when more than two numbers are missing or duplicated because partitioning becomes ambiguous.
- For more complex cases, other algorithms not based on XOR are needed.
Key Terms & Definitions
- XOR (Exclusive OR) — A bitwise logical operation where the result is 1 if the bits differ, 0 if the same.
- Commutative property — Changing the order of operands does not affect the result.
- Associative property — Grouping of operands does not affect the result.
- Forward Error Correction (FEC) — Technique for correcting data errors by sending extra redundant data (often using XOR).
Action Items / Next Steps
- Practice implementing XOR-based algorithms for swapping, missing number, and duplicate detection problems.
- Read up on Forward Error Correction for deeper understanding.
- Optional: Explore how to generalize these techniques or their limitations.