Why does this swap using simple addition and subtraction won't overflow?

2

I was under the impression that only swap using X-OR would work when we are providing inputs that are close to max limit of integer. Surprisingly this simple swap using addition and subtraction is working with those inputs too.

#include <iostream>

void simple_swap(int &x, int &y) {
    x += y;
    y = x - y;
    x -= y;
}

int main() {
    int a = 10; int b = 15;

    /* Testing integer overflow, sum has 1 bit outside of 4-bytes integer limit */
    a = 0xFFFFFFFF;     // a is 2^32-1 = 4294967295
    b = 0xFFFFFFFE;     // b is 2^32-2 = 4294967294

    std::cout << "Before swap " << "a = " << (unsigned int)a << ", b=" << (unsigned int)b << std::endl;
    simple_swap(a, b);
    std::cout << "After swap " << "a = " << (unsigned int)a << ", b=" << (unsigned int)b << std::endl;

    return 0;
}

I'm using Visual Studio 2013. If you are using a different compiler and the code does not work as showed in output let me know in comments.

I'm interested in knowing the reason behind this. Is compiler replacing the code with something else?

c++
visual-studio
asked on Stack Overflow May 24, 2015 by Atiq Rahman

2 Answers

5

Swap using addition

Even if it seems to work it's a bad idea.

void simple_swap(int &x, int &y) {
    x += y;
    y = x - y;
    x -= y;
}

if both x and y are really big or really small you'll get integer overflow/underflow which is undefined behavior. That means even if it seems to work for you there aren't any guarantees that it will work for anyone else or even when you compile it the next time. It can just break from one moment to the other.

Swap using xor

Also just for the record, using xor for swapping is broken too, for a whole different reason though.

void simple_swap(int &x, int &y) {
    x ^= y;
    y ^= x;
    x ^= y;
}

works most of the time but if you were to try and swap a variable with itself it would break:

simple_swap(a, a);

void simple_swap(int &x, int &y) { // both x and y refer to the same variable (a).
    x ^= y; // both variables will be 0 after this statement.
    y ^= x;
    x ^= y;
}

Now swapping a variable with itself might seem dumb and unlikely but you don't always know. It could be two pointers that just happen to point to the same variable and suddenly you got a weird bug. To make sure that it'd always work you'd have to make it overly complicated and test that both parameters aren't actually the same.

void simple_swap(int &x, int &y) {
    if ( x != y) {
        x ^= y;
        y ^= x;
        x ^= y;
    }
}

harder to read than such a simple function should be and not as simple as one thinks at first.

The correct way

Just use the simple and easy correct way, don't try to be clever:

void simple_swap(int &x, int &y) {
    int temp = x;
    x = y;
    y = temp;
}

Swapping is simple, every compiler will be able to optimize it to the best version.

answered on Stack Overflow May 24, 2015 by user1942027 • edited May 24, 2015 by user1942027
0

Working through the operations, the mathematical values result in a correct swap, disregarding the possibility of overflow.

The operations used, in 2's complement, maintain the invariant that the value is the "true mathematical value" modulo 2^(word_size_in_bytes).

Since there is only one residue modulo 2^(word-size-in-bytes) of any "true mathematical value", the swap is guaranteed to exchange the values (whatever they may represent).

Of course, 2's complement is not guaranteed by the C or C++ standards. It's just what's done in >99.9999% of CPUs.

answered on Stack Overflow May 24, 2015 by Atsby

User contributions licensed under CC BY-SA 3.0