Странное поведение при смене XOR при обнулении данных - PullRequest
Новая
       8

Странное поведение при смене XOR при обнулении данных

3 голосов
/ 26 апреля 2011

Спасибо, Даг. Вот исправление: 

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 делал что-то странное.

Я напечатал данные до и после того, как поменял их, и вот что они напечатали: 

...

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

Я не использовал никаких ссылок для кода быстрой сортировки, поэтому он может быть неправильным, но я не думаю, что это имеет отношение к проблеме.

Ответы [ 3 ]

17 голосов
/ 26 апреля 2011

Ваш своп a и b находятся в одном месте.Хак XOR работает только тогда, когда они находятся в разных местах.

Я думаю, в 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
1 голос
/ 26 апреля 2011

В дополнение к существующим ответам, я просто добавлю, что если вы собираетесь сделать тест перед заменой, то вы также можете изменить: 

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, что может сэкономить некоторую ненужную замену.

0 голосов
/ 26 апреля 2011

Все, что xor'd с самим собой, равно нулю.

...