XOR Operations Collection
Comprehensive collection of XOR (exclusive OR) bit manipulation techniques with unique mathematical properties: a ⊕ a = 0 (self-inverse), a ⊕ 0 = a (identity), commutative, and associative. XOR is fundamental in finding unique/missing elements, in-place swapping, parity checking, cryptography, error detection, and many optimization problems. These elegant properties make XOR one of the most powerful bitwise operators.
Visualization
Interactive visualization for XOR Operations Collection
XOR Operations:
- • Bit-by-bit exclusive OR
- • a XOR a = 0
- • a XOR 0 = a
Interactive visualization with step-by-step execution
Implementation
1// Find unique number (all others appear twice)
2function findUnique(arr: number[]): number {
3 let result = 0;
4 for (const num of arr) {
5 result ^= num;
6 }
7 return result;
8}
9
10// Swap without temp variable
11function swapXOR(a: number, b: number): [number, number] {
12 if (a !== b) {
13 a ^= b;
14 b ^= a;
15 a ^= b;
16 }
17 return [a, b];
18}
19
20// Check if two numbers differ at position k
21function bitsDiffer(a: number, b: number, k: number): boolean {
22 return ((a ^ b) & (1 << k)) !== 0;
23}Deep Dive
Theoretical Foundation
XOR (exclusive OR) outputs 1 when bits differ, 0 when same. Its mathematical properties create elegant algorithms: (1) Self-inverse: a ⊕ a = 0 enables duplicate cancellation, (2) Identity: a ⊕ 0 = a preserves value, (3) Commutative: a ⊕ b = b ⊕ a allows any order, (4) Associative: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) enables grouping. Combining these: if all elements appear twice except one, XORing all cancels pairs leaving unique element. For finding missing number in [0,n], XOR all array elements with all numbers 0 to n - pairs cancel, missing remains. XOR swap works because a⊕b⊕b = a. These properties make XOR invaluable in constrained-space problems.
Complexity
Time
O(1)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Finding missing/unique numbers in arrays
Simple encryption/decryption (XOR cipher)
Parity bit calculation in error detection
RAID data recovery (XOR parity)
Network packet checksums
Gray code generation
Random number generation (XORshift)
Fast hash functions
Bit flipping in graphics
Use Cases
Related Algorithms
Count Set Bits (Brian Kernighan's Algorithm)
Efficiently count the number of 1 bits (set bits) in the binary representation of an integer. Brian Kernighan's algorithm is one of the most elegant bit manipulation techniques, invented by Brian Kernighan (co-author of 'The C Programming Language'). The algorithm repeatedly clears the rightmost set bit, making it optimal as it only loops for the number of set bits rather than all bits.
Check if Power of Two
Determine if a given integer is a power of 2 using a brilliant single bitwise operation. Powers of 2 in binary have exactly one set bit: 1=0001, 2=0010, 4=0100, 8=1000, 16=10000. This unique property enables an O(1) constant-time check using the elegant formula: n > 0 && (n & (n-1)) == 0. This trick is widely used in systems programming, memory management, and optimization.
Reverse Bits
Reverse the bit pattern of a 32-bit unsigned integer efficiently using bit manipulation. For example, 43261596 (binary: 00000010100101000001111010011100) becomes 964176192 (binary: 00111001011110000010100101000000) after reversal. This operation is critical in Fast Fourier Transform (FFT) bit-reversal permutation, graphics processing, cryptographic operations, and understanding little-endian/big-endian conversions at the bit level.
Add Two Numbers (Bitwise)
Perform integer addition using only bitwise operations (XOR, AND, shift) without the + operator, mimicking how CPUs add numbers at the hardware level using logic gates. This algorithm decomposes addition into sum-without-carry (XOR) and carry-generation (AND + shift), iterating until no carry remains. Fundamental for understanding computer architecture, ALU design, and implementing arithmetic when + operator is unavailable or expensive.