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) return; // если указатели равны
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

Если сравнить этот код с тем, как обычно делается обмен переменных местами мы увидим, что и там и там 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, значение останется неизменным.

aba ^ b
000
011
101
110

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

aba ^ b ^ b
000
010
101
111

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

ШагПеременная aПеременная b
0ab
1a ^ bb
2a ^ bb ^ a ^ b
3a ^ b ^ b ^ a ^ bb ^ 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) return; // если указатели равны
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

Аналогичный подход:

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

Недостатком такого обмена является то, что может произойти переполнение. В случае языка программирования Си (стандарт C99) корректная работа этого алгоритма гарантирована только для беззнаковых целых чисел. На практике алгоритм будет корректно работать с любыми целочисленными типами данных, потому что эти типы данных можно рассматривать как абелевы группы по сложению, а в них, как известно, обратные элементы однозначны.

Пример

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

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

Шагab
06553010
1410
2465530
31065530

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

  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 © Александр Майоров. Все права защищены. Копирование материалов с сайта без письменного разрешения автора запрещено.