Swapping Values with Bitwise XOR Operations
The XOR operation, denoted as ^ in most programming languages, produces a true output only when the inputs differ. Its truth table is as follows:
| p | q | p ^ q |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Examples of XOR on binary literals:
bin(0b1010 ^ 0b1100) # Result: '0b110'
bin(0b11110000 ^ 0b10101010) # Result: '0b1011010'
Bitwise XOR is both associative and commutative:
(x ^ y) ^ z == x ^ (y ^ z) and x ^ y == y ^ x.
Two fundamental properties arise:
- XOR with zero yields the original value:
x ^ 0 == x. - XOR of a value with itself yields zero:
x ^ x == 0.
These properties enable swapping two integer variables without a temporary variable.
Swapping Algorithm:
Given two integesr val1 and val2:
val1 = val1 ^ val2
val2 = val1 ^ val2 # Now val2 holds the original value of val1
val1 = val1 ^ val2 # Now val1 holds the original value of val2
Step-by-step derivation:
- After first line:
val1 = original_val1 ^ original_val2. - Second line computes:
val2 = (original_val1 ^ original_val2) ^ original_val2 = original_val1 ^ (original_val2 ^ original_val2) = original_val1 ^ 0 = original_val1. - Third line computes:
val1 = (original_val1 ^ original_val2) ^ original_val1 = (original_val1 ^ original_val1) ^ original_val2 = 0 ^ original_val2 = original_val2.
While Python supports tuple packing/unpacking (val1, val2 = val2, val1), the XOR method demonstrates bitwise manipulation principles.
Critical Limitation: This technique fails when the two operands reference the same memory location.
Example where it works (dsitinct variables):
x = 5
y = 3
x ^= y
y ^= x
x ^= y
# Result: x == 3, y == 5
Example where it fails (same array element):
def unsafe_swap(list_data, idx1, idx2):
list_data[idx1] ^= list_data[idx2]
list_data[idx2] ^= list_data[idx1]
list_data[idx1] ^= list_data[idx2]
arr = [10, 20]
unsafe_swap(arr, 0, 0) # Swaps element with itself
print(arr) # Output: [0, 20] (Incorrect! Element zero becomes 0)
When idx1 == idx2, the steps become:
arr[0] = arr[0] ^ arr[0] # 10 ^ 10 = 0
arr[0] = arr[0] ^ arr[0] # 0 ^ 0 = 0
arr[0] = arr[0] ^ arr[0] # 0 ^ 0 = 0
The element is erroneously zeroed. Always ensure operands are distinct when using this swap method.
