[C# Helper]
Index Books FAQ Contact About Rod
[Essential Algorithms, Second Edition]

[The Modern C# Challenge]

[WPF 3d, Three-Dimensional Graphics with WPF and C#]

[The C# Helper Top 100]

[Interview Puzzles Dissected]

[C# 24-Hour Trainer]

[Beginning Software Engineering]

[C# 5.0 Programmer's Reference]

[MCSD Certification Toolkit (Exam 70-483): Programming in C#]

Title: Use XOR to swap two numbers in C#

[Use XOR to swap two numbers in C#]

Note that I don't recommend this technique for swapping numbers. It's mostly a clever trick that provides a lesson in the bitwise XOR operation. The code is much easier to understand if you just declare a temporary variable to make the swap.

This example uses the following code to swap two numbers without creating a temporary variable. If variables A and B originally hold values a and b, then the comments to the right of the code explain how the swap works.

// Swap the numbers. A = A ^ B; // A holds a ^ b. B = B ^ A; // B holds b ^ (a ^ b) = b ^ b ^ a = 0 ^ a = a. A = A ^ B; // A holds (a ^ b) ^ a = a ^ a ^ b = b.

The first statement makes A hold a ^ b.

The second statement makes B hold b ^ A. Because A now holds a ^ b, this is b ^ (a ^ b). The XOR operator is commutative (you can change the order of two operands) so this is the same as b ^ (b ^ a). XOR is also associative (you can change where the parentheses are) so this is the same as (b ^ b) ^ a. For any value b, b ^ b = 0 so this is the same as 0 ^ a. Finally for any value a, 0 ^ a = a. So when this statement is done executing, variable B holds the value a.

The third statement makes A hold A ^ B. Plugging in the current values held by the variables, this is (a ^ b) ^ a. Using the commutative and associative properties again, and the fact that a ^ a = 0 and 0 ^ b = b, this is the same as b.

When all three lines are finished, variable A holds value b and variable B holds value a.

You can use a similar trick with other operators that are commutative, associative, and invertible. For example, you can perform the swap with the * and / operators or with the + and - operators. For an exercise, give it a try. The XOR operator has the advantage that it won't cause overflow.

Download the example to experiment with it and to see additional details.

© 2009-2022 Rocky Mountain Computer Consulting, Inc. All rights reserved.