☕ DSA Java Articles

Topics › Bit Manipulation › Learn Bit Manipulation

Swap Two Numbers

Easy TUF ID 1005 A2Z

Java source ↗ Edit this article ↗

Problem

You are given two integers a and b. Exchange their values so that a holds what b held and b holds what a held. The interesting version of the question forbids a third variable: do it with arithmetic or with XOR alone.

Constraints: a and b are 32-bit signed integers; the result must be correct even when a + b overflows.

A note on Java before the examples. Java passes every argument by value, so a method swap(int a, int b) can only swap its own local copies; the caller’s variables are untouched. The methods in the Java file therefore return {a, b} after performing the swap, and a separate method swaps two slots of an array, which is the form you actually use in sorting and partitioning code.

Example 1

a = 3, b = 5
answer = a = 5, b = 3

Example 2

a = 7, b = 7
answer = a = 7, b = 7     // equal values must survive; the XOR trick only fails when both names share one storage slot

Example 3

a = 2000000000, b = 2000000000
answer = a = 2000000000, b = 2000000000   // a + b overflows int, yet the arithmetic swap still works in Java

Approach 1: A temporary variable

Intuition. Only one of the two values can be moved at a time, and moving it overwrites the other. Park one value somewhere first. This is the version to write in real code: it is obvious, it works for any type, and the compiler emits the same three moves the clever versions compile to anyway.

Algorithm.

  1. temp = a.
  2. a = b.
  3. b = temp.
static int[] usingTemp(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
    return new int[]{a, b};
}

Complexity. Time O(1), three assignments. Space O(1), one extra word.

Approach 2: Arithmetic, store the sum

Intuition. If a is overwritten with a + b, nothing is lost: b is still there, so the original a can be recovered as (a + b) - b, and once b holds the original a, the original b is (a + b) - a. Each step is reversible, so the information is never destroyed, it is just encoded.

Algorithm. Write a0, b0 for the original values.

  1. a = a + b, so a = a0 + b0.
  2. b = a - b, so b = (a0 + b0) - b0 = a0.
  3. a = a - b, so a = (a0 + b0) - a0 = b0.
static int[] usingArithmetic(int a, int b) {
    a = a + b;        // a holds a0 + b0
    b = a - b;        // (a0 + b0) - b0 = a0
    a = a - b;        // (a0 + b0) - a0 = b0
    return new int[]{a, b};
}

Complexity. Time O(1), space O(1).

What about overflow? 2000000000 + 2000000000 does not fit in an int and wraps to -294967296. In Java this is not a bug: int arithmetic is defined to be modulo 2^32, and subtraction undoes addition modulo 2^32 just as it does for ordinary integers. -294967296 - 2000000000 wraps back to 2000000000, and so does the final subtraction. The test with Integer.MAX_VALUE and Integer.MIN_VALUE passes for the same reason. The trick is nevertheless dangerous in C and C++, where signed overflow is undefined behaviour, and it does not work for floating point, where (a + b) - b can differ from a by rounding. A multiplication-based variant (a *= b; b = a / b; a = a / b) is strictly worse: it divides by zero when either value is 0.

Approach 3: Optimal, XOR

Intuition. XOR has two properties that make it a reversible encoding: x ^ x = 0 and x ^ 0 = x, and it is associative and commutative. Store a ^ b in a; then XOR-ing it with b cancels the b and leaves a0, and XOR-ing it with a0 cancels the a0 and leaves b0. Unlike the sum, XOR works bit by bit with no carries, so there is nothing to overflow, and it is the version interviewers mean by “swap using bit manipulation”.

Algorithm.

  1. a = a ^ b, so a = a0 ^ b0.
  2. b = a ^ b, so b = (a0 ^ b0) ^ b0 = a0.
  3. a = a ^ b, so a = (a0 ^ b0) ^ a0 = b0.
static int[] usingXor(int a, int b) {
    a = a ^ b;        // a holds a0 ^ b0
    b = a ^ b;        // (a0 ^ b0) ^ b0 = a0
    a = a ^ b;        // (a0 ^ b0) ^ a0 = b0
    return new int[]{a, b};
}

Dry run on a = 3 = 011, b = 5 = 101:

step a b
start 011 (3) 101 (5)
a ^= b 110 (6) 101 (5)
b ^= a 110 (6) 011 (3)
a ^= b 101 (5) 011 (3)

Complexity. Time O(1), space O(1).

Swapping inside an array, and the one real trap

In practice you swap two slots, arr[i] and arr[j], and the XOR form becomes arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]. This hides a trap that the two-variable version cannot show. If i == j, both names refer to the same memory. The first XOR computes arr[i] ^ arr[i] = 0 and stores it, and the original value is gone; the next two XORs of zero with zero leave zero. The slot has been wiped. The arithmetic swap has the same problem in a subtler form (arr[i] doubles, then becomes 0).

static void swapInArray(int[] arr, int i, int j) {
    if (i == j) return;
    arr[i] ^= arr[j];
    arr[j] ^= arr[i];
    arr[i] ^= arr[j];
}

static void swapInArrayUnguarded(int[] arr, int i, int j) {
    arr[i] ^= arr[j];
    arr[j] ^= arr[i];
    arr[i] ^= arr[j];
}

The Java file demonstrates both: swapInArray(arr, 1, 1) leaves the array alone, swapInArrayUnguarded(arr, 1, 1) sets arr[1] to 0. Partition loops in quicksort routinely call swap with i == j, so the unguarded XOR swap is a genuine production bug, not a curiosity. The temp-variable swap has no such problem, which is one more reason it is the default.

Edge cases and pitfalls