Problem Statement

Swapping two numbers is a common task in programming, often requiring the use of temporary variable. However, what if want to perform this swap without using any additional memory? The goal is to exchange the values of two variables without relying on an extra variable.

Understanding the Problem

Traditional swapping involves the use of a third variable to temporarily store one value while we overwrite it with the second value. Bit manipulation provides an interesting avenue to achieve the same result without introducing an additional variable.

Consider two variables, a and b, with initial values. The task is to swap the values of these variables without using any third variable.

Example:

Let's say we have a = 7 and b = 3. The expected result after swapping should be a = 3 and b = 7.

Solution

1️⃣ Traditional Solution (Using Extra Variable):

In traditional solution we uses an temporary variable to store one's value, while it is being overwritten by the others. and then write this temporary value to the second.

int temp = a;
a = b;
b = temp;

2️⃣ Solution with Bit Manipulation: (Using XOR)

The XOR operator (^) can be used to swap two numbers without any additional variable. Here's how it works:

1. a = a ^ b: XOR both numbers and store the result in a.
2. b = a ^ b: XOR the result with b to get the original value of a.
3. a = a ^ b: XOR the result with b (now a) to get the original value of b.

Dry Run:

Initialization:

a = 5 (Binary: 0101)
b = 10 (Binary: 1010)

Step 1:

a = a ^ b
a = 5 ^ 10
a = 0101 ^ 1010

a = 1111 (15 in decimal)
yet, b = 1010 (10 in decimal)

Step 2:

a = 1111 (15 in decimal)
b = 1010 (10 in decimal)

b = a ^ b
  = 15 ^ 10
  = 1111 ^ 1010
  = 0101, (which is 5 in decimal)

a is still = 1111 (15 in decimal)

Step 3:

a = 1111 (15 in decimal)
b = 0101 (5 in decimal)

a = a ^ b
  = 15 ^ 5
  = 1111 ^ 0101
  = 1010, (which is 10 in decimal).
  
Thus the values get swapped.

Code:

#include <iostream>

void swapWithoutTemp(int &a, int &b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

int main() {
    int a = 5, b = 7;

    std::cout << "Before Swap: a = " << a << ", b = " << b << std::endl;

    swapWithoutTemp(a, b);

    std::cout << "After Swap:  a = " << a << ", b = " << b << std::endl;

    return 0;
}

// Output
Before Swap: a = 5, b = 7
After Swap:  a = 7, b = 5

3️⃣ Method 3: Using Arithmetic Operations

You can also swap two numbers using addition and subtraction. The key is to modify one number by adding the other, and then subtracting to isolate the original values.

1. a = a + b: Sum both numbers and store it in a.
2. b = a - b: Subtract b from the sum to get the original value of a.
3. a = a - b: Subtract the new value of b from the sum to get the original value of b.

Code:

#include <iostream>
using namespace std;

int main() {
    int a = 5, b = 10;

    cout << "Before swapping: a = " << a << ", b = " << b << endl;

    // Swap using arithmetic operations
    a = a + b;  // Step 1: a becomes 15 (5 + 10)
    b = a - b;  // Step 2: b becomes 5 (15 - 10)
    a = a - b;  // Step 3: a becomes 10 (15 - 5)

    cout << "After swapping: a = " << a << ", b = " << b << endl;

    return 0;
}