I've seen a lot of techniques for swapping two variables without using a third.
Swap two variables without using a temp variable
How to swap two numbers without using third variable? [duplicate]
Swap 2 values of 2 variables without using a third variable; python
Swap two variables value without using third variable in php [duplicate]
How to swap two numbers without using temp variables or arithmetic operations?
Are any of these faster than using the third variable?
No. At least in Java. Swapping two primitive integers using a third variable is the fastest (and easiest to understand).
I wrote this code to test it. It compares the two most common techniques I found in various answers: swapping using subtraction and swapping using bitwise xor.
package compareswapmethods;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class CompareSwapMethods {
private static final Random rand = new Random();
private static final int ITERATIONS = 1000000;
private static final int MIN_LENGTH = 2;
private static final int MAX_LENGTH = 100;
private static final int MIN_VAL = -100;
private static final int MAX_VAL = 100;
public static void main(String[] args)
{
System.out.println("press enter to start");
Scanner in = new Scanner(System.in);
in.nextLine();
for(int i = 0; i < ITERATIONS; i++)
{
int[] sample1, sample2, sample3;
sample1 = generateRandomArray(MIN_LENGTH, MAX_LENGTH, MIN_VAL, MAX_VAL);
sample2 = Arrays.copyOf(sample1, sample1.length);
sample3 = Arrays.copyOf(sample1, sample2.length);
/*System.out.println(Arrays.toString(sample1));
System.out.println(Arrays.toString(sample2));
System.out.println(Arrays.toString(sample3));*/
int x = randomVal(0, sample1.length-1);
int y = randomVal(0, sample1.length-1);
thirdv(sample1, x, y);
subtractive(sample2, x, y);
bitwise(sample3, x, y);
/*System.out.println(Arrays.toString(sample1));
System.out.println(Arrays.toString(sample2));
System.out.println(Arrays.toString(sample3));
System.out.println("-");*/
}
System.out.println("done");
}
/*swap elements in array using third variable*/
public static void thirdv(int[] arr, int x, int y)
{
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
/*swap elements in array using subtraction variable*/
public static void subtractive(int[] arr, int x, int y)
{
arr[x] = arr[x] + arr[y];
arr[y] = arr[x] - arr[y];
arr[x] = arr[x] - arr[y];
}
/*swap elements in array using bitwise xor*/
public static void bitwise(int[] arr, int x, int y)
{
arr[x] ^= arr[y];
arr[y] ^= arr[x];
arr[x] ^= arr[y];
}
/*returns random int between [min, max]*/
public static int randomVal(int min, int max)
{
return min + rand.nextInt(max - min + 1);
}
/*creates array of random length, between [min, max],
and calls poppulateArray on it*/
public static int[] generateRandomArray(int minLength, int maxLength, int minVal, int maxVal)
{
int[] arr = new int[minLength+rand.nextInt((maxLength-minLength)+1)];
populateArray(arr, minVal, maxVal);
return arr;
}
/*assigns random values, in the range of [min, max]
(inclusive), to the elements in arr*/
public static void populateArray(int arr[], int min, int max)
{
Random r = new Random();
for(int i = 0; i < arr.length; i++)
arr[i] = min+r.nextInt((max-min)+1);
}
}
I then used VisualVM to profile and here are the results:
Results do very a bit between tests but I've always seen the thirdv method take the shortest amount of CPU time.
no even in computer archtecture point of view.
for example, if i use bit manipulation to swap two integer like following:
a ^= b;
b ^= a;
a ^= b;
what running in CPU is that:
mov reg1, &a
mov reg2, &b
xor reg1, reg2
xor reg2, reg1
xor reg1, reg2
what can tell easily is that reg1 and reg2 rely on each other.
modern CPUs use disorder execution of instruction stream. that is, execute more than one instructions if these instructions do not rely on the result of each other. therefore, it's normal for modern CPUs run multiple instructions at the same moment.
but what if you use a temp variable? dead easy. modern CPUs usually have instruction level support.
xchg reg1, reg2
done.
BTW, don't pay too much attention to the assembly. it varies in different architectures. just for demo.
