XOR swap in Python
Swapping x and y with three XORs, x ^= y, y ^= x, x ^= y, without a temporary; fails if x and y alias the same location.
- File
xor_swap.py, 23 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/xor-swap/. The authors are listed in prov/G8X0J3.jsonl.
def xor_swap(a: list[int], i: int, j: int) -> None:
"""Exchange a[i] and a[j] in place with three XORs and no temporary.
The items are integers. Python's ^ acts on the infinite two's complement
form, so the swap is also correct for negative integers and for words of
any width. When i == j nothing changes. Cost: O(1) word operations.
"""
if i == j: # @line L1
return
a[i] ^= a[j] # @line L2
a[j] ^= a[i] # @line L3
a[i] ^= a[j] # @line L4
def xor_swap_unguarded(a: list[int], i: int, j: int) -> None:
"""The same three XORs without the test of line L1 (zeroes a[i] when i == j)."""
a[i] ^= a[j]
a[j] ^= a[i]
a[i] ^= a[j]
test_xor_swap.py 48 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/xor-swap/. The authors are listed in prov/G8X0J3.jsonl.
import random
from xor_swap import xor_swap, xor_swap_unguarded
def test_example() -> None:
a = [180, 105]
xor_swap(a, 0, 1)
assert a == [105, 180]
def test_all_8_bit_pairs() -> None:
for x in range(256):
for y in range(256):
a = [x, y, 7]
xor_swap(a, 0, 1)
assert a == [y, x, 7]
def test_same_cell() -> None:
for x in range(256):
a = [x]
xor_swap(a, 0, 0)
assert a == [x]
b = [x]
xor_swap_unguarded(b, 0, 0)
assert b == [0]
def test_negative_and_wide() -> None:
a = [-5, 2**64 - 1]
xor_swap(a, 0, 1)
assert a == [2**64 - 1, -5]
def test_random_against_tuple_swap() -> None:
rng = random.Random(20)
for _ in range(2000):
n = rng.randrange(1, 8)
a = [rng.randrange(-(2**63), 2**64) for _ in range(n)]
i, j = rng.randrange(n), rng.randrange(n)
want = list(a)
want[i], want[j] = want[j], want[i]
xor_swap(a, i, j)
assert a == want
What the next level needs
- the tests did not run in this build