Блог

Главная - Вопросы по программированию - Странное поведение подкачки XOR при обнулении данных

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

#c #swap #quicksort #xor

#c #подкачка #быстрая сортировка #xor

Вопрос:

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

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

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

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

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

 ...

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]) amp;amp; a[indx3] >= min(a[indx1], a[indx2]))
        return indx3;

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

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

void swap(intamp; a, intamp; 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 amp;amp; 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();
}

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

Комментарии:

1. Использование этого XOR на самом деле может быть медленнее, чем обычная подкачка двух значений с использованием переменной temp; тот факт, что вы пишете через ссылки, предполагает, что вы заставляете компилятор выполнять 3 записи в память (ок, строка кэша), тогда как swamp в стиле temp должен выполнять только две записи в память (любой интеллектуальный компилятор поместит temp в регистры). Добавление условной проверки, безусловно, замедляет работу. Так что, хотя это может быть забавно, это, вероятно, непрактично делать в sort.

2. верно, но подкачка xor предназначена не для ускорения, а для того, чтобы избежать временного. В этом случае я бы сказал, что конечная причина — повеселиться.

3. Гораздо лучшее решение — не использовать xor-swap; это медленно .

Ответ №1:

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

Я думаю, на C; вот таблица:

            amp;a != amp;b  amp;a == amp;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

Ответ №2:

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

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

Для:

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

Это обработает случай, когда amp;a == amp;b а также случай, когда a == b , что может сэкономить некоторую ненужную подкачку.

Ответ №3:

Все, что было изменено с самим собой, равно нулю.