How does XOR variable swapping work?

by

You can see how it works by doing the substitution:

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

Substituting,

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

Because xor is fully associative and commutative:

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

Since x xor x == 0 for any x,

y2 = x0 xor 0
x2 = 0 xor 0 xor y0

And since x xor 0 == x for any x,

y2 = x0
x2 = y0

And the swap is done.

More Related Contents:

  1. What are bitwise shift (bit-shift) operators and how do they work?
  2. Given an integer, how do I find the next largest power of two using bit-twiddling?
  3. XOR of three values
  4. What is a magic number, and why is it bad? [closed]
  5. Why shouldn’t I use “Hungarian Notation”?
  6. Why should hash functions use a prime number modulus?
  7. Prefer composition over inheritance?
  8. Why is XOR the default way to combine hashes?
  9. Singletons: good design or a crutch? [closed]
  10. What is Type-safe?
  11. Test loops at the top or bottom? (while vs. do while) [closed]
  12. Solving “Who owns the Zebra” programmatically?
  13. Try to describe polymorphism as easy as you can [closed]
  14. Pass by reference or pass by value? [closed]
  15. How do I assess the hash collision probability?
  16. When to use unsigned values over signed ones?
  17. Making a system call that returns the stdout output as a string
  18. When is it okay to check if a file exists?
  19. What is eager loading?
  20. Private vs. Public members in practice (how important is encapsulation?) [closed]
  21. Why is writing a closed TCP socket worse than reading one?
  22. Bitwise XOR of hexadecimal numbers
  23. How to deal with constructor over-injection in .NET
  24. How to calculate distance from a point to a line segment, on a sphere?
  25. Followup: Finding an accurate “distance” between colors
  26. What’s the term for the part of the URL after the question mark?
  27. Is bit shifting O(1) or O(n)?
  28. C Programming – XOR Bitwise Operation
  29. Why are leading zeroes used to represent octal numbers?
  30. What is differential execution?

Leave a Comment