XOR Properties

Introduction

The XOR (exclusive OR) operation is one of the most versatile bitwise operations in programming. Represented by the ^ symbol in most programming languages, XOR returns 1 if the corresponding bits of its operands are different and 0 if they're the same.

XOR has several intriguing mathematical properties that make it incredibly useful for solving various programming problems efficiently. Understanding these properties can help you develop elegant solutions to complex problems and optimize your code.

Basic XOR Operation

Before diving into the properties, let's understand how XOR works at the bit level:

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

In code, XOR is typically represented with the ^ operator:

java

int a = 5;      // binary: 101
int b = 3;      // binary: 011
int result = a ^ b;  // binary: 110 = decimal: 6
System.out.println(result);  // Output: 6

Key XOR Properties

1. Self-Inverse Property (XOR with same value)

When a value is XORed with itself, the result is always 0.

A ^ A = 0

python

a = 42
result = a ^ a
print(result)  # Output: 0

This works for any value of a because each bit is XORed with itself, producing 0.

2. XOR with Zero

XORing any value with 0 returns the value unchanged.

A ^ 0 = A

python

a = 42
result = a ^ 0
print(result)  # Output: 42

3. Commutativity

The order of operands doesn't matter in XOR operations.

A ^ B = B ^ A

cpp

int a = 25;
int b = 17;
cout << (a ^ b) << endl;  // Output: 8
cout << (b ^ a) << endl;  // Output: 8 (same result)

4. Associativity

When chaining multiple XOR operations, the grouping doesn't affect the result.

(A ^ B) ^ C = A ^ (B ^ C)

javascript

const a = 10;
const b = 20;
const c = 30;
console.log((a ^ b) ^ c);  // Output: 16
console.log(a ^ (b ^ c));  // Output: 16

5. Cancellation Property

XORing a sequence with the same value twice cancels out the effect.

A ^ B ^ B = A

This is derived from properties 1 and 3. Since B ^ B = 0 and A ^ 0 = A, we get A ^ B ^ B = A ^ 0 = A.

python

a = 42
b = 17
result = a ^ b ^ b
print(result)  # Output: 42 (back to the original value of a)

Practical Applications

1. Swapping Variables Without a Temporary Variable

cpp

int a = 5;
int b = 7;

// Swap without a temp variable
a = a ^ b;
b = a ^ b;  // Now b = a
a = a ^ b;  // Now a = b

std::cout << "a: " << a << ", b: " << b << std::endl;  // Output: a: 7, b: 5

How this works:

1. After a = a ^ b, a contains a ^ b.
2. When b = a ^ b, we get b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a.
3. Finally, a = a ^ b gives us a = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b.

2. Finding a Non-Duplicated Element

Given an array where every element appears exactly twice except one element, find the unique element.

java

public static int findUnique(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

// Test
int[] arr = {4, 2, 7, 4, 8, 2, 7};
System.out.println(findUnique(arr));  // Output: 8

This works because the duplicated elements cancel each other out (A ^ A = 0), and only the unique element remains (0 ^ A = A).

3. Memory-Efficient Toggle

XOR can be used to toggle bits efficiently:

c

// Toggle the 3rd bit (0-indexed)
int num = 42;          // binary: 101010
int mask = 1 << 3;     // binary: 001000
num = num ^ mask;      // binary: 100010 = decimal: 34
printf("%d\n", num);   // Output: 34

// Toggle it back
num = num ^ mask;      // binary: 101010 = decimal: 42
printf("%d\n", num);   // Output: 42

4. Simple Encryption/Decryption

XOR can be used for basic encryption and decryption:

python

def xor_encrypt(message, key):
    encrypted = ""
    for char in message:
        encrypted += chr(ord(char) ^ key)
    return encrypted

def xor_decrypt(encrypted, key):
    return xor_encrypt(encrypted, key)  # Same operation for both!

# Example
message = "Hello World"
key = 42
encrypted = xor_encrypt(message, key)
print("Encrypted:", encrypted)

decrypted = xor_decrypt(encrypted, key)
print("Decrypted:", decrypted)  # Output: Hello World

This works because of the cancellation property: (A ^ key) ^ key = A.

5. Computing Parity

You can check if a number has an odd or even number of set bits (1s) using XOR:

javascript

function hasOddParity(num) {
    let parity = 0;
    while (num > 0) {
        parity ^= (num & 1);  // XOR with least significant bit
        num >>= 1;            // Right shift by 1
    }
    return parity === 1;      // True if odd number of 1s, false otherwise
}

console.log(hasOddParity(7));  // 7 is 111 in binary, has 3 set bits, Output: true
console.log(hasOddParity(15)); // 15 is 1111 in binary, has 4 set bits, Output: false

Performance Considerations

XOR operations are very efficient because they're directly supported by CPU hardware. Most processors can execute XOR operations in a single clock cycle for register-sized operands. This makes XOR-based algorithms particularly fast.

When dealing with large datasets or performance-critical code, leveraging XOR properties can lead to significant optimizations.

Common Mistakes and Pitfalls

1. Assuming XOR is logical exclusive OR: In some contexts, XOR refers to the logical operation, but in bit manipulation, it operates on each bit independently.

2. Forgetting operator precedence: XOR (^) has lower precedence than equality operators, so remember to use parentheses when needed.

3. Overcomplicating solutions: Sometimes developers miss opportunities to use XOR for elegant solutions and end up with more complex code.

Summary

XOR is a powerful bitwise operation with several useful properties:

• Self-inverse: A ^ A = 0
• Identity with zero: A ^ 0 = A
• Commutativity: A ^ B = B ^ A
• Associativity: (A ^ B) ^ C = A ^ (B ^ C)
• Cancellation: A ^ B ^ B = A

These properties make XOR invaluable for various applications, from efficient variable swapping and finding unique elements to basic encryption and bit toggling.

Practice Exercises

1. Write a function to determine if two integers have the same sign without using conditional statements.
2. Given an array where all elements appear three times except for one element, find the element that appears only once.
3. Implement a function that returns the XOR of all integers from 1 to n efficiently.
4. Use XOR to create a function that checks if exactly one of two boolean variables is true.
5. Implement a function that finds the missing number in an array containing n-1 distinct numbers from the range [0, n].

Further Reading

• Bit manipulation techniques beyond XOR
• Applications of XOR in cryptography
• XOR-based data structures like XOR linked lists
• XOR in network protocols and error detection

By mastering XOR properties, you'll add a powerful tool to your programming toolkit that can help you solve many problems more efficiently and elegantly.