XOR-swap или как поменять переменные местами без временной переменной

Для того, чтобы поменять местами информацию из 2 блоков памяти совершенно не обязательно копировать один из них, записывать в него второй блок, а затем сохранённое значение записывать во второй блок.

Казалось бы, это невозможно сделать, потому что как можно “запомнить”, что было в ячейке до перезаписи. Машина ведь не может “жонглировать” переменными или параллельно читать и записывать в одни и те же переменные.

Обмен переменных с помощью xor

int main() {
    int a = 2, b = 5;
    a ^= b;
    b ^= a;
    a ^= b;
    printf("a = %d, b = %d\n", a, b); // a = 5, b = 2
    return 0;
}

В виде функции:

void swapInts(int* a, int* b) {
    if (a != b) {
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
    else {
        // если указатели равны, мы не можем делать xor, так как тогда значение обнулится
        // x ^ x = 0 для любого x
        int temp = *a;
        *a = *b;
        *b = temp;
    }
}

Если сравнить этот код с тем, как обычно делается обмен переменных местами мы увидим, что и там и там 3 операции.

int main() {
    int a = 2, b = 5;
    int temp = a;
    a = b;
    b = temp;
    printf("a = %d, b = %d\n", a, b); // a = 5, b = 2
    return 0;
}

Однако в первом случае дополнительная память на стеке не выделяется.

Стоит отметить, что на практике обмен значений с помощью xor применяется редко, так как вследствие архитектуры регистров большинства процессоров, копирование данных произойдёт быстрее. Но есть специфические случаи, когда обмен с помощью xor гораздо эффективнее. Если требуется поменять местами 2 больших блока памяти, такой тип обмена является предпочтительным.

Доказательство корректности

По законам математической логики, операция xor является коммутативной и ассоциативной.

Это очевидно, ведь таблица истинности для xor симметрична, то есть если мы поменяем местами колонки a и b, значение останется неизменным.

a b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0

Докажем, что a ^ b ^ b = a верно для любых a и b.

a b a ^ b ^ b
0 0 0
0 1 0
1 0 1
1 1 1

Рассмотрим последовательность действий в алгоритме по шагам. В таблице указаны изначальные значения a и b.

Шаг Переменная a Переменная b
0 a b
1 a ^ b b
2 a ^ b b ^ a ^ b
3 a ^ b ^ b ^ a ^ b b ^ a ^ b

Таким образом, в переменной a теперь значение a ^ b ^ b ^ a ^ b.

Используя тот факт, что a ^ b ^ b = a верно для любых a и b преобразуем это выражение:

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

Аналогично для переменной b:

b ^ a ^ b = a

Таким образом, в переменной a теперь находится изначальное значение b, а в переменной b находится значение a, то есть переменные поменяны местами.

Аналогичный обмен с помощью арифметики

void swapInts(int* a, int* b) {
    if (a != b) {
        *a = *a + *b;
        *b = *a - *b;
        *a = *a - *b;
    }
    else {
        // если указатели равны, мы не можем делать xor, так как тогда значение обнулится
        // x ^ x = 0 для любого x
        int temp = *a;
        *a = *b;
        *b = temp;
    }
}

В данном случае возможен аналогичный подход:

a = a - b;
b = a + b;
a = b - a;

Недостатком такого обмена является то, что может произойти переполнение.

Однако это переполнение никак не помешает, если используются беззнаковые типы данных, так как при арифметических операциях с беззнаковыми числами при переполнении значения “пойдут по кругу” и по сути информация не потеряется.

Пример

Изначальные значения a и b: 65530 и 10 соответственно.

Тип данных: беззнаковый short (занимает 2 байта, максимальное значение 65535).

Шаг a b
0 65530 10
1 4 10
2 4 65530
3 10 65530

Рассмотрим шаги подробнее:

  1. a = a + b

    65530 + 10 = 65540

    a = 65540 % 65536 = 4

  2. b = a - b

    4 - 10 = -6

    b = 65536 - 6 = 65530

  3. a = a - b

    4 - 65530 = -65526

    a = 65536 - 65526 = 10


Copyright © 2019 Александр Майоров. Все права защищены.