Monday, April 16, 2018

Swap two numbers in Java without temporary variable

Swap two numbers Java

There are mainly 3 approaches to swap two number in Java, we will discuss all of them in order of increasing relevancy from interview point of view.

Approach 1. Using a temporary variable

Two numbers can be swapped using a temporary variable.
void method3() {
    int x = 10, y = 5;

    int temp = x;
    x = y;
    y = temp;
    System.out.println("After swap x = " + x + ", y = " + y);
}
Program output
After swap x = 5, y = 10
But this approach is not of great relevance from interview point of view.

Without temp variable

Approach 2. Using sum of numbers

We can easily swap two numbers using summation approach, as illustrated in the below code snippet.
void method1() {
    int x = 10, y = 5;

    x = x + y; // x becomes 15
    y = x - y; // y becomes 15 - 5 = 10
    x = x - y; // x becomes 15 - 10 = 5
    System.out.println("After swap x = " + x + ", y = " + y);
}
But there are issues with this code due to integer overflow and underflow. This program will not behave as expected when sum of x and y crosses the (+/-)231 limit.
Integer overflow & underflow
If it overflows, it goes back to the minimum value (Integer.MIN_VALUE = -231) and continues from there. If it underflows, it goes back to the maximum value (Integer.MAX_VALUE = 231) and continues from there. The main issue here is that overflow and underflow are silent and you will not see any exceptions if it occurs.
Integer overflow example:
void integerOverflow() {
    int x = Integer.MAX_VALUE - 10;
    int y = Integer.MAX_VALUE - 10;
    int result = x + y;    
    System.out.println("sum = " + result);
}
Since variable result can not hold sum of two large integer values, so integer overflow will occur. Please be noted that there will be no exception, so user will never be notified about this behavior.
Program output
sum = -22
Did you know
Java 8 provides option to let programmer know about the underflow and overflow by making use of the new Math#addExact() and Math#subtractExact() methods which will throw an ArithmeticException on overflow/underflow.
Java 8 approach (safe approach)
public static boolean willAdditionOverflow(int left, int right) {
    try {
        Math.addExact(left, right);
        return false;
    } catch (ArithmeticException e) {
        return true;
    }
}

Approach 3. Using XOR bitwise operator

Best way to swap two numbers without falling into trap of integer overflow problem is to use XOR bitwise operator.
What is Bitwise XOR
A bitwise XOR takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same.
    0101 (decimal 2)
XOR 0011 (decimal 10)
    ----
  = 0110 (decimal 8)
Bitwise XOR Practical Use
Bitwise XOR can be used to flip the bits in a given number. Any bit may be toggled by XORing it with 1.
Java Code to swap two integer using XOR
void method2() {
    int x = 10;
    int y = 5;

    // Code to swap 'x' (1010) and 'y' (0101)
    x = x ^ y; // x now becomes 15 (1111)
    y = x ^ y; // y becomes 10 (1010)
    x = x ^ y; // x becomes 5 (0101)

    System.out.println("After swap: x = " + x + ", y = " + y);
}
Program output
After swap: x = 5, y = 10
That’s all.

Practical Usecase of Bitwise OR, AND and XOR operand

Bitwise AND
The operation may be used to determine whether a particular bit is set (1) or clear (0).
Bitwise OR
The bitwise OR may be used to set to 1 the selected bits of the register described above.
Bitwise XOR
The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip). Any bit may be toggled by XORing it with 1.

No comments:

Post a Comment

Your comment will be published after review from moderator