Короткие заметки о математике и программировании

xor

Операция XOR

Конспект
✍️Побитовая XOR объединяет два числа в третье
✍️Полезное тождество: a ^ b ^ a = b ^ a ^ a = b
✍️Обозначения: ⊕, ^, xor; «сумма по модулю 2»; либо A, либо B, но не оба
✍️Свойства: ассоциативность (a^(b^c)=(a^b)^c), коммутативность (a^b=b^a), самоуничтожение (x^a^a=x)
✍️Википедия: исключающее "или"

Лекция
Раньше мы упоминали немного «мистический» способ обмена значений двух переменных с помощью оператора XOR. Чтобы объяснить этот эффект, мы сначала разобрали двоичную систему счисления и таблицу перевода между базой 2 и базой 10. Теперь разберём саму операцию XOR.

Это полезная операция, поэтому у неё несколько обозначений: ⊕, ^, xor. На одиночных битах она ведёт себя как «сумма по модулю 2»: результат равен 0, когда аргументы равны, и 1, когда они различны. Таблица истинности для двух битов — 0110.

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

Пример: 5 ^ 3. В двоичном виде: 101 ^ 011. По столбцам: 1^0=1, 0^1=1, 1^1=0 → 110, то есть 6. Проверьте в консоли браузера: console.log(5 ^ 3).

Построим 8×8‑таблицу XOR для значений 0…7:

|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 |
| 2 | 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 |
| 3 | 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 |
| 4 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
| 5 | 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
| 6 | 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
| 7 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |

Проверим алгоритм обмена через XOR. Пусть a = 5, b = 4. Проследим значения после присваиваний:

a = a ^ b  // a = 5 ^ 4 = 1, b = 4
b = a ^ b  // a = 1, b = 1 ^ 4 = 5
a = a ^ b  // a = 1 ^ 5 = 4, b = 5

Видно, что алгоритм работает: значения обменялись без временной переменной.

#education #devTopic #junior