Mastering XOR Magic: Essential Party Tricks for Every Programmer
The XOR operation, or exclusive OR, holds a simple but powerful property: applying XOR with the same value twice restores the original. Mathematically, for any bits A and B, A XOR B XOR B = A. This idempotent behavior—where the operation is its own inverse—gives rise to a host of clever programming hacks. Let’s explore these “party tricks” that demonstrate XOR’s elegance, from quick demos to data structure innovations.
Verifying the Core Property in Python
Section titled “Verifying the Core Property in Python”To see this in action, fire up Python and test all bit combinations:
for a in range(2): for b in range(2): assert a ^ b ^ b == a, f"Failed for a={a}, b={b}"print("XOR property holds for all 1-bit cases!")Since it works per bit, it scales to entire integers. This foundation enables everything that follows.
XOR as a Rudimentary Encryption Tool
Section titled “XOR as a Rudimentary Encryption Tool”XOR shines in symmetric encryption. Convert a message like “hello world” to integers, XOR each with a key (say, 69), and you’ve got ciphertext. Decrypt by XORing again with the same key:
def encrypt(message, key): return ''.join(chr(ord(c) ^ key) for c in message)
msg = "hello world"key = 69encrypted = encrypt(msg, key)decrypted = encrypt(encrypted, key)print(decrypted) # Back to "hello world"
wrong_key_decrypt = encrypt(encrypted, 42) # Gibberish!This is a toy example—vulnerable to frequency analysis and known-plaintext attacks. Never use it in production, but it’s a good illustration of XOR’s reversibility.
Swapping Variables Without a Temp (Even in C)
Section titled “Swapping Variables Without a Temp (Even in C)”Modern languages like Python allow a, b = b, a. In C, without multiple assignment, XOR does the heavy lifting:
#include <stdio.h>
int main() { int a = 69, b = 420; printf("Before: a=%d, b=%d\n", a, b);
a ^= b; // a = 69 ^ 420 b ^= a; // b = 420 ^ (69 ^ 420) = 69 a ^= b; // a = (69 ^ 420) ^ 69 = 420
printf("After: a=%d, b=%d\n", a, b); return 0;}No extra variables needed! Compilers optimize anyway, but this bitwise dance is a classic interview flex. (Pro tip: Addition-based swaps like a += b; b = a - b; a -= b; exist too, but XOR avoids overflow.)
Detecting the Duplicate in an Unsorted Array
Section titled “Detecting the Duplicate in an Unsorted Array”Given numbers 1 to 100 with one duplicate (array size 101), find it in O(n) time without sorting. XOR all expected numbers (1^2^…^100), then XOR with array elements. Unique pairs cancel; the duplicate remains:
#include <stdio.h>#include <stdlib.h>#include <time.h>
int main() { srand(time(NULL)); int arr[101]; // 1-100 + one dupe // Populate randomly with dupe (omitted for brevity)
int x = 0; for (int i = 1; i <= 100; ++i) x ^= i; for (int i = 0; i < 101; ++i) x ^= arr[i]; printf("Duplicate: %d\n", x); return 0;}Brilliant for its constant space and linear time. Interviews love it—though it reveals more about memorization than skill.
The XOR Linked List: Half the Pointer Overhead
Section titled “The XOR Linked List: Half the Pointer Overhead”Doubly linked lists store prev and next pointers per node, doubling pointer memory. XOR them into one field (zord = prev ^ next), halving usage (payload excluded).
Node traversal: Start with prev = NULL, compute next = zord ^ prev, print/update prev = current.
Here’s a minimal C implementation:
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdint.h>#include <assert.h>
typedef struct Node { int value; uintptr_t zord; // Size of pointer, XOR of prev ^ next} Node;
Node* node_create(int value) { Node* node = malloc(sizeof(*node)); memset(node, 0, sizeof(*node)); node->value = value; return node;}
typedef struct LinkedList { Node* begin; Node* end;} LinkedList;
void list_append(LinkedList* list, int value) { Node* new_node = node_create(value); if (!list->end) { // Empty list list->begin = list->end = new_node; return; } // Link to end list->end->zord ^= (uintptr_t)new_node; new_node->zord = (uintptr_t)list->end; list->end = new_node;}
Node* node_next(Node** prev_ptr, Node* curr) { Node* next = (Node*)(curr->zord ^ (uintptr_t)*prev_ptr); *prev_ptr = curr; return next;}
int main() { LinkedList list = {0}; for (int i = 5; i <= 10; ++i) { list_append(&list, i); }
Node* prev = NULL; Node* it = list.begin; do { printf("%d ", it->value); it = node_next(&prev, it); } while (it); printf("\n"); // 5 6 7 8 9 10 return 0;}Bonus: Start from end with prev = NULL for reverse traversal. Null endpoints simplify edge cases (zord == 0 means isolated).
Why XOR Deserves Your Attention
Section titled “Why XOR Deserves Your Attention”These tricks, while not production staples, sharpen bitwise intuition. The property A XOR B XOR B = A (or x ^ 0 = x) is XOR’s superpower—commutative, associative, and self-inverse. Next coding interview, dazzle with it. Got more XOR hacks? The bit manipulation well runs deep.