为什么使用简单加法和减法的交换不会溢出？

Question

我的印象是,当我们提供接近最大整数限制的输入时,只使用X-OR进行交换.令人惊讶的是,使用加法和减法的这种简单交换也适用于那些输入.

#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;
}

我正在使用Visual Studio 2013.如果您使用的是其他编译器且代码无法正常输出,请在评论中告诉我.

我很想知道这背后的原因.编译器是否用其他东西替换代码？

Answer 1

使用添加交换

即使它似乎工作,这是一个坏主意.

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

如果两个x和y是非常大或非常小的,你会得到整数溢出/下溢这是不确定的行为.这意味着即使它似乎对你有用,也没有任何保证它可以为其他人工作,甚至在你下次编译时也是如此.它可以从一个时刻到另一个时刻.

使用xor交换

同样只是为了记录,使用xor进行交换也被打破了,但完全不同的原因.

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

大部分时间工作,但如果你试图与自己交换变量,它会破坏:

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;
}

现在用自己交换一个变量可能看起来很愚蠢而且不太可能,但你并不总是知道.它可能是两个指针恰好指向同一个变量,突然间你得到了一个奇怪的错误.为了确保它始终有效,你必须使它过于复杂并测试两个参数实际上并不相同.

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

比起这样一个简单的函数更难读,而不是像最初想的那么简单.

正确的方法

只需使用简单易行的方法,不要试图聪明:

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

交换很简单,每个编译器都能够将其优化到最佳版本.