Swap Two Numbers using XOR - Visualization

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given two integer values x and y, your task is to swap their values without using a temporary variable.

This technique makes use of the XOR bitwise operation to exchange the values in-place, making it both efficient and space-saving.

Return an array with the swapped values in the format [x, y].

Examples❯

x y Output Description
5 10 [10, 5] Standard positive integers; values swapped using XOR
0 7 [7, 0] One of the values is 0; XOR still works as expected
-3 4 [4, -3] XOR handles negative and positive integers correctly
100 100 [100, 100] Swapping identical values results in the same values
-1 -99 [-99, -1] Negative values swapped using XOR; bitwise logic still valid
2147483647 -2147483648 [-2147483648, 2147483647] Edge case: maximum and minimum 32-bit signed integers swapped
"" 5 [5, 0] Empty input for x treated as 0; swap proceeds
3 "" [0, 3] Empty input for y treated as 0; swap proceeds
"" "" [0, 0] Both inputs empty; treated as 0, swap has no effect

Solution❯

Understanding the Problem

We are given two integers, x and y. Our goal is to swap their values — that is, after the swap, x should hold the original value of y and y should hold the original value of x.

However, we are not allowed to use a temporary variable to hold one of the values during the swap. This means we must find a way to perform the swap in-place, using only arithmetic or bitwise operations.

We will use the XOR (^) bitwise operator to solve this problem. XOR has a unique property: applying XOR twice with the same value restores the original number.

Step-by-Step Solution with Example

Step 1: Start with two numbers

Let’s say we have x = 4 and y = 7. Our goal is to swap them using XOR.

Binary representation:

  • 4 is 0100
  • 7 is 0111

Step 2: Perform x = x ^ y

Now x becomes:

x = 4 ^ 7 = 0100 ^ 0111 = 0011 → x = 3

Now, x = 3 and y = 7

Step 3: Perform y = x ^ y

Now we use the new x (which is 3) to update y:

y = 3 ^ 7 = 0011 ^ 0111 = 0100 → y = 4

Now, x = 3 and y = 4

Step 4: Perform x = x ^ y

Use the new y to update x:

x = 3 ^ 4 = 0011 ^ 0100 = 0111 → x = 7

Now, x = 7 and y = 4

Step 5: Final Output

We have successfully swapped the values. The output is:

[7, 4]

Edge Cases

  • Same numbers: If x and y are the same (e.g., x = y = 5), the XOR trick still works and the values remain unchanged.
  • Zero involved: XOR works fine even if one or both values are 0. For example, x = 0, y = 9 swaps correctly to [9, 0].
  • Negative numbers: The XOR operation works at the bit level, so it can also handle negative integers correctly.
  • Large numbers: XOR is a bitwise operation, so it can handle large integers within the bounds of your programming language’s integer type without overflow.

Final Thoughts

Swapping two numbers using XOR is a neat trick that avoids using extra memory. It's commonly asked in technical interviews to test understanding of bitwise operations and in-place algorithms.

However, for general code readability and safety, especially in production, using a temporary variable is often preferred unless you're working under strict memory constraints.

Still, this is a powerful technique worth knowing and practicing!

Algorithm Steps❯

  1. Apply XOR to x and y: x = x ^ y.
  2. Update y using the new value of x: y = x ^ y.
  3. Update x using the updated value of y: x = x ^ y.
  4. Now, x and y have been swapped.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

void swapXOR(int* x, int* y) {
    if (x != y) { // prevent issues if both pointers point to same address
        *x = *x ^ *y;
        *y = *x ^ *y;
        *x = *x ^ *y;
    }
}

int main() {
    int a = 5, b = 9;
    printf("Before swap: a = %d, b = %d\n", a, b);
    swapXOR(&a, &b);
    printf("After swap:  a = %d, b = %d\n", a, b);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The algorithm performs a fixed number of bitwise XOR operations (3 in total), regardless of the input values. Therefore, the time complexity is constant in the best case.
Average CaseO(1)Since the number of operations does not depend on the input size or value, the average-case time complexity remains constant.
Worst CaseO(1)In the worst case, the algorithm still only performs 3 XOR operations, which takes constant time, hence O(1).

Space Complexity❯

O(1)

Explanation: The swap is performed in-place using XOR without any additional memory allocation. No temporary variables are used, so space complexity is constant.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...