清零数据时出现奇怪的异或交换行为

Question

谢谢Doug。这是修复方法：

void swap(int& a, int& b) {
    if (&a == &b) // added this check to ensure the same address is not passed in
        return;

    a ^= b;
    b ^= a;
    a ^= b;
}

我正在用C++实现快速排序，使用整数作为虚拟数据。我之前一直使用异或交换算法来原地交换两个值，但我发现我的排序出了问题。我更改了我的交换算法并使其正常工作。我添加了一些调试语句，发现异或交换正在做一些奇怪的事情。

我打印出交换前后的数据，结果如下：

...

swapping -5, -3
swapped  -3, -5

swapping -5, -5
swapped  0, 0     <---- What?

swapping -2, -4
swapped  -4, -2

...

以下是我的代码：

// this might not be that great or even work as intended but it doesn't really matter for this problem
int av3index(int a[], int indx1, int indx2, int indx3) {
    if (a[indx3] <= max(a[indx1], a[indx2]) && a[indx3] >= min(a[indx1], a[indx2]))
        return indx3;

    if (a[indx2] <= max(a[indx1], a[indx3]) && a[indx2] >= min(a[indx1], a[indx3]))
        return indx2;

    if (a[indx1] <= max(a[indx2], a[indx3]) && a[indx1] >= min(a[indx2], a[indx3]))
        return indx1;
}

void swap(int& a, int& b) {
    /*
    This works
    int tmp = b;
    b = a;
    a = tmp;*/

    cout << "swapping " << a << ", " << b << endl;

    a ^= b;
    b ^= a;
    a ^= b;

    cout << "swapped  " << a << ", " << b << endl << endl;
}

void zqsort(int a[], int len) {
    if (len <= 1)
        return;

    int pivot = av3index(a, 0, len / 2, len - 1);

    swap(a[pivot], a[0]);

    int i = 1, j = len - 1;

    while (i <= j) {
        if (a[i] > a[0]) {
            while (i <= j && a[j] > a[0])
                --j;

            if (i <= j)
                swap(a[i], a[j]);
        }

        ++i;
    }

    swap(a[0], a[j]);

    zqsort(a, len / 2);
    zqsort(a + len / 2, len - len / 2);
}

int main() {
    int values[] = {5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5};

    int len = sizeof(values) / sizeof(int);

    int* arr = new int[len];

    for (int i = 0; i < len; ++i)
        arr[i] = values[i];

    zqsort(arr, len);

    cout << "sorted array:" << endl;
    for (int i = 0; i < len; ++i)
        cout << arr[i] << endl;

    cin.get();
}

对于快速排序代码，我没有使用任何参考资料，所以可能有错误，但我认为这与问题无关。

- Tom Sykes

---

使用这种异或交换方式可能比使用临时变量的传统交换方式更慢；通过使用引用进行写操作会强制编译器执行三个内存写操作（好的，缓存行操作），而使用临时变量的交换方式只需要执行两个内存写操作（任何智能编译器都会将临时变量放入寄存器中）。添加条件检查肯定会使其变慢。因此，虽然这可能很有趣，但在排序中实际上并不实用。 - Ira Baxter

真的，但是异或交换并不是为了加速，而是为了避免使用临时变量。在这种情况下，我想最终的原因是为了好玩。 - Michael Krelin - hacker

一个更好的解决方案是不要使用异或交换；它很慢。 - Peter Cordes

Answer 1

您想要交换 a 和 b 的值，但它们在同一个位置。XOR hack 只有在它们在不同的位置时才有效。

我认为这是 C 语言; 这里有一个表格：

           &a != &b  &a == &b
           *a   *b   *a   *b
           -5   -5   -5   -5
*a ^= *b;   0   -5    0    0
*b ^= *a;   0   -5    0    0
*a ^= *b;  -5   -5    0    0

- Doug Currie

Answer 2

除了现有的答案，我想补充一点，如果你在交换之前要进行测试，那么你最好也更改一下：

if (&a == &b) // added this check to ensure the same address is not passed in
    return;

至：

if (a == b) // check that values are different
    return;

这将处理 &a == &b 和 a == b 的情况，这可能会节省一些不必要的交换。

- Paul R

Answer 3

任何数与自身异或的结果都是零。

- Jeff Paquette