Фокусы программирования

Аватар пользователя Vadim Sakovich
Систематизация и связи
Логика

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

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

В программировании на языках близких к ассемблеру это делается при помощи трёх операторов XOR (исключающее ИЛИ):

a := a XOR b
b := a XOR b
a := a XOR b

После этого содержимое a и b поменяются местами. Тут := - это знак оператора присваивания: переменная слева от знака,  получает значение результата операции справа от знака :=.

В Википедии есть описания этой процедуры и на русском, и на английском языках. Здесь, чтобы не углубляться в нюансы, можно условно предположить, что a и b - это просто битовые строки длиной в байт, хотя на ассемблере это могут быть и области памяти в тысячи байтов.

Вопрос у меня, как всегда, простейший: приходилось ли кому-нибудь из форумских логиков встречать упоминания о другом возможном способе такого же обмена областями памяти без использования дополнительной?  ( : А то я снова чувствую себя одиноко - покинутым мировым логическим сообществом программистов. : )

Комментарии

Аватар пользователя Vadim Sakovich

Странно, что форум наш наполнен до верху логикой и логиками, причём во всех мыслимых логических ипостасях, а вот чисто логическая (простейшая!) задачка - поставила всех в тупик.

Но, это не столь важно, потому что в тысячу раз непонятнее тот факт, что никто не может привести хоть какую ссылку, где был бы ответ... ещё раз - на простейший вопрос: каким ещё способом можно обменять содержимое  a и b местами, не используя промежуточной памяти.

Я знаю как, но не может быть, чтобы никто этого не знал! Не может быть, потому что этого не может быть никогда! А раз так, то мне снова надо к психиатру. Однако, у меня есть некие потуги на догадку почему это так. И это связано именно с обсуждаемыми ранее принципиальными положениями о том, что все виды так называемых "логик" (включая математическую) НЕ ЯВЛЯЮТСЯ самостоятельными формальными дисциплинами в математическом смысле. Они - такие же прикладные дисциплины, как и электронные схемы, программирование, и пр. - всё то, что "откусывает" понравившуюся часть от по-настоящему формальной дисциплины - булевой алгебры (булевого исчисления).

И это не беда. Беда, когда формальная логика НАВЯЗЫВАЕТ своё видение, суёт свою морду с разными там "истинами", ПРЕПЯТСТВУЯ тем самым  пониманию действительно совершенно абстрактной дисциплины - булевого исчисления.

Как приложение к поставленному в теме вопросу, добавляю элементарщину. В надежде, что эта элементащина породит такой же элементарный ответ на поставленную задачу. Итак, к трём представленным операциям исключающее Или прилагаю таблицу "истинностей", чтобы можно было проследить процесс "меняния" местами a с b.

Аватар пользователя Виктор Володин

a := a ≡ b
b := a ≡ b
a := a ≡ b

Аватар пользователя Vadim Sakovich

Отлично. Знак ≡ - это знак булевой операции эквиваленция (↔).

Просьба - хоть какой-нибудь источник, plz, где хотя бы упоминалось об этом!

Всё то же, но для операции эквиваленция:

Аватар пользователя Виктор Володин

Vadim Sakovich, 1 Март, 2021 - 10:02, ссылка

Просьба - хоть какой-нибудь источник, plz, где хотя бы упоминалось об этом!

Не знаю. Программирование - это область практических приемов. Если известен практический работающий прием, зачем придумывать другой? К тому же, в большинстве компьютеров нет команды ≡.

Аватар пользователя Vadim Sakovich

К тому же, в большинстве компьютеров нет команды ≡.

Так потому-то и нет, что математики искусственно сужают базис. Более того - с высоко поднятой головой плодят суженные базисы и гордятся этим, не понимая, что прячут под ковёр такие закономерности ПОЛНОГО БАЗИСА, которые делают булеву алгебру по-настоящему логичной и даже - более практичной.

Аватар пользователя Чифу

В х86 есть специальная команда обмена операндами XCHG R1, R2.

Для пояснения обмена команда XOR еще называется "сумма по модулю 2", т.е. сначала получается "сумма" A и B, потом из нее "вычитается" В, получается А, потом из суммы "вычитается" А, получается В.

Эквивалентность является дополнительной к XOR операцией.