c++ - 为什么这种使用简单加减法的交换不会溢出？

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 进行交换也被破坏了，尽管原因完全不同。

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

交换很简单，每个编译器都可以将其优化到最佳版本。