Approach to Swapping Two Numbers Using XOR (an interesting example of bit manipulation)

241

Approach to Swapping Two Numbers Using XOR

The XOR swap technique is a clever way to swap two numbers without using a temporary variable. This method leverages the properties of the XOR bitwise operation, which has unique characteristics:

  1. XOR Properties:
    • ( a ⊕ a = 0 ) (any number XORed with itself is zero)
    • ( a ⊕ 0 = a ) (any number XORed with zero is the number itself)
    • XOR is commutative and associative, meaning the order of operations does not matter.

Why It Works

The XOR swap works in three steps:

  1. First Step: a = a ^ b

    • Here, a now holds the XOR of a and b. This means that a contains information about both original values.

  2. Second Step: b = a ^ b

    • In this step, b is updated to the original value of a. This works because:
      • b now becomes a ^ b ^ b, which simplifies to a (since ( b ⊕ b = 0 )).

  3. Third Step: a = a ^ b

    • Finally, a is updated to the original value of b. This works because:
      • a now becomes a ^ b ^ a, which simplifies to b.

Output Example

Here’s the output you would see when running the provided C++ code:

Before swapping: a = 5, b = 10
After swapping: a = 10, b = 5

Sample Dry Run of XOR Swap

Let's perform a dry run of the XOR swap technique using the numbers ( a = 5 ) and ( b = 10 ).

Initial Values

  • ( a = 5 ) (in binary: 0101)
  • ( b = 10 ) (in binary: 1010)

Step 1: a = a ^ b

  • Calculation:
    • ( a = 5 ⊕ 10 )
    • ( 0101 ⊕ 1010 = 1111 ) (in decimal: 15)
  • Updated Values:
    • ( a = 15 )
    • ( b = 10 )

Step 2: b = a ^ b

  • Calculation:
    • ( b = 15 ⊕ 10 )
    • ( 1111 ⊕ 1010 = 0101 ) (in decimal: 5)
  • Updated Values:
    • ( a = 15 )
    • ( b = 5 )

Step 3: a = a ^ b

  • Calculation:
    • ( a = 15 ⊕ 5 )
    • ( 1111 ⊕ 0101 = 1010 ) (in decimal: 10)
  • Updated Values:
    • ( a = 10 )
    • ( b = 5 )

Final Values

  • After the swap:
    • ( a = 10 )
    • ( b = 5 )

Summary of Dry Run

  • Before swapping: ( a = 5, b = 10 )
  • After swapping: ( a = 10, b = 5 )

This dry run illustrates how the XOR swap technique effectively swaps the values of two variables without using a temporary variable.

The XOR swap is an efficient way to swap two numbers without needing extra space for a temporary variable. It is particularly useful in low-level programming and situations where memory usage is critical. However, it is essential to ensure that the two numbers are not the same before performing the swap to avoid zeroing them out.