奇怪的XOR交换行为,同时清零数据 [英] Weird XOR swap behavior while zeroing out data
问题描述
谢谢Doug。这里是修复:
Thanks Doug. Here's the fix:
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 ++中实现快乐的乐趣,我使用整数的虚拟数据。我一直在使用XOR交换算法来交换两个值到位,但我注意到我的排序是拧紧。我改变了我的交换算法,它的工作。我添加了一些调试语句,发现XOR交换正在做一些奇怪的事情。
I am implementing quicksort for fun in C++, and I am using integers for dummy data. I had been using the XOR swapping algorithm to swap two values in place, but I noticed my sort was screwing up. I changed my swapping algorithm and it worked. I added some debugging statements, and found that the XOR swap was doing something weird.
我在交换之前和之后打印了数据,这是它打印的:
I printed the data before and after I swapped it, and this is what it printed:
...
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();
}
我没有使用quicksort代码的任何引用,所以它可能是错误的,但我不认为这与问题密切相关。
I didn't use any references for the quicksort code so it might be wrong, but I don't think that's germane to the problem.
推荐答案
您的互换 a
和 b
是相同的位置。 XOR黑客只有在他们在不同的位置时才有效。
Your swap a
and b
are the same location. The XOR hack only works when they are different locations.
我想在C;这里有一个表格:
I think in C; here's a table:
&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
这篇关于奇怪的XOR交换行为,同时清零数据的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!