Allocating memory to n-dim Array on heap
June 13, 2012
Time and Speed puzzle
June 13, 2012

How to swap 2 variables witout using third

The usual method of swapping two numbers, using a temporaty variable is as shown below.

    // Swapping 2 int, X & Y using temporary variable t
    int t = X;
    X = Y;
    Y = t;

How will you swap two numbers without using a temporary variable?

Solution:

Using XOR operator

    X = X ^ Y;
    Y = X ^ Y;
    X = X ^ Y;

The disadvantage of this method is that it can only be applied to low-level data types like integers & characters (char, short, int, long).

C & C++ does not allow bit-wise operation on non-integral operands.

Using +,- operators

    X = X + Y;
    Y = X - Y;
    X = X - Y;

This method can only be applied on numerical values (cannot swap two struct or array objects using this method).

The issue of arithmetic overflow will also be there.

For example: If integers are stored in 2 bytes, then the maximum value an int variable can hold will be 32767. Consider below example:

    int x = 32760;
    int y = 20;
    x = x+y;    // ERROR.. Out of range undefined
    x = x-y;
    x = x-y;

You will say that the values will move in circle (i.e 32767 + 1 = -32768). But that’s not correct. Overflow (and underflow) behavior in C/C++ is undefined. Hence, compiler can implement it whatever way they want.

If a question is asked that what will be the final values of x and y in above code, the correct answer is “UNDEFINED”.. Hence, the code will not be able to swap x and y.

Using *,/ operators

Similar to above method

Note: None of the above methods (including the method using temporary variable in the question) will work for all cases. For example, if you have an object of a complex class. Then swapping using temporary variable will only do a shallow copying, for those cases you will have to overload assignment operator and copy constructor.

1 Comment

  1. slaffiguaks says:

    Wonderful Post.thanks for share..a lot more wait..

Leave a Reply

Your email address will not be published. Required fields are marked *