Один хороший фокус с XOR - двунаправленный список

Побитовое "исключающее или" (xor, ^) - функция, горячо любимая всеми, кто "копошится в железяках", потому как с её помощью можно сделать много чего полезного и красивого.

Свойства xor следующие:

• коммутативность: X^Y = Y^X 
• ассоциативность: (X^Y)^Z = X^(Y^Z)
• наличие нейтрального элемента: существует такое Z, что X^Z=X для любых значений X
• инверсия: для любого значения W существует такое M, что W^M=Z, кроме того, известно, что каждое значение инверсно само себе, т.е. W^W=Z

Самый известный прием использования xor - экономный обмен содержимым двух ячеек памяти (или переменных, кому как нравится), не требующий использования третьей ячейки. Обычно процедура обмена реализуется как раз через дополнительную ячейку памяти, например, надо обменять содержимое ячеек A и B:

A->C ; содержимое A копируем в С
B->A ; содержимое B копируем в A
C->B ; содержимое A из дополнительной ячейки копируем в B

Кстати, до сих пор не могу понять авторов ассемблеров - зачем для одной и той же операции пересылки использовать то мнемонику mov, то cp, то ещё что, если суть операции отлично отражается указанными символами?

С помощью xor то же самое делается так:

A^B->A ; побитовое исключающее или содержимого A и B, результат записывается в A
A^B->B ; побитовое исключающее или содержимого A и B, результат записывается в B
A^B->A ; побитовое исключающее или содержимого A и B, результат записывается в A

Почему так получается, вытекает из указанных выше свойств xor:

после первой операции в A содержится A^B
после второй операции в B содержится (A^B)^B = A^(B^B) = A^Z = A
после третьей операции в A содержится (A^B)^A = B^(A^A) = B^Z = B

Одна ячейка памяти - вроде чепуха, но не для тех, кто программирует микроконтроллеры или вообще встраиваемые вычислители.

А вот - менее известный, совершенно жуткий в каком-то смысле (и не одном) хак, но зато до чего изящный.

Двунаправленный список требует для работы хранения двух адресов в каждом элементе списка - предыдущего и следующего элементов. Мы говорим список - понимаем "динамически выделяемая память" (а иначе зачем он вообще), говорим "динамически выделяемая память" - понимаем RAM, говорим RAM - понимаем "дорогой ресурс". Причем не просто дорогой, а часто - бесценный. В микроконтроллерах, например, обычно объем RAM измеряется в сотнях слов. Соответственно, два адреса в каждом элементе списка - это может быть просто непозволительно "жирно".
В подобных случаях можно с помощью фокуса с XOR добиться экономии, и существенной, если хранить в элементе списка результат такой операции: адрес_предыдущего_элемента^адрес_следующего_элемента.

Модель всего этого дела будет такой (&X - адрес X, ну а X{} условимся считать чем-то вроде структуры X, если говорить в терминах C):

A{ссылка: ...^&B } B{ссылка: &A^&C} C{ссылка: &B^...}

Предположим, что текущая ячейка - B. Для работы алгоритма знание только текущего адреса недостаточно, надо "помнить" еще и адрес предыдущей-следующей ячейки, в зависимости от направления обхода списка. 

Тогда адрес элемента, следующего за B, находится так:

&A ^ B.ссылка

потому что &A^(&A^&C) = (&A^&A)^&C = Z ^ &C = &C

Адрес элемента, предшествующего (в списке) B, находится аналогично:

&C ^ B.ссылка

потому что &C^(&A^&C) = (&C^&C)^&A = Z ^ &A = &A

Можно оценить экономию: если максимальная длина списка - N элементов, такой метод позволяет уменьшить требуемый объем ОЗУ на N-1 слов (потому что для вычисления адресов при обходе требуется два указателя на соседние элементы, а не один). Для микроконтроллеров с RISC-ядром и разрядностью адреса, бОльшей, чем машинное слово, может получиться весьма ощутимая цифра.

Правда, отлаживать такое - ещё то удовольствие, но, например, в крохотном мониторе (ядром операционной системы подобное называть - много чести) реального времени такая структура данных может быть очень полезной.

PS

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

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365