Swap по-новому

  • 9
  • Недоступна
В классе Pair реализуй метод swap, который должен для x, y менять местами их значения. Можно использовать только операции: 1) Исключающее или. 2) Присваивание. 3) Исключающее или с присваиванием. Не оставляй комментарии, не меняй остальной код.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (46)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
LuneFox богатый программист в далёких мечтах Expert
1 декабря, 20:14
Ничоси, я сам догадался, как это сделать :) Сначала думал, что всё безнадёжно, и придётся снова лезть в комментарии, но всё-таки взял ручку с листочком и начал думать... Скажем, у нас есть число 27 (11011) и число 13 (01101), для начала просто попробуем сделать между ними XOR:
  00011011 (27)
  00001101 (13)
^ --------
  00010110 (22)
Обращаем внимание, что если смотреть на получившиеся группы цифр по вертикали, там всегда присутствуют либо две единицы или один нолик, либо три нуля (варианты - 110, 101, 011, 000, они же и есть таблица истинности для XOR). Попробуем XOR-нуть оригинальные числа с результатом (22):
  00011011 (27)        00001101 (13)
  00010110 (22)        00010110 (22)
^ --------           ^ --------
  00001101 (13)        00011011 (27) 
Убеждаемся, что вертикальные группы всё так же состоят либо из двух единиц и нолика, либо из трёх нулей, и делаем вывод, что имея только два числа из трёх (двух оригинальных, и одного полученного через XOR), мы всегда сможем восстановить третье. Видим 1 и 1 - значит, не хватает 0, видим 1 и 0 - значит не хватет 1, видим 0 и 0 - значит, не хватает 0. Таким образом, для решения этой задачи достаточно сделать всего 3 шага. Для удобства первый результат XOR между двумя числами X и Y я буду звать "ключом", потому что он нужен только временно, чтобы поменять местами две переменные. 1) Записываем в X ключ (🔑X = X XOR Y), временно теряем X (ничего страшного, у нас есть ключ) 2) Восстанавливаем в Y оригинальный X, совместив Y с ключом (Y = Y XOR 🔑X) 3) Восстанавливаем в X оригинальный Y, совместив то, что записано в Y с ключом (X = 🔑X XOR Y) Готово! Теперь в X лежит Y, а Y лежит в X. Кстати, если я не ошибаюсь, как-то так работает RAID-3, где всегда можно восстановить информацию на битом диске, воспользовавшись параллельными данными из двух других дисков. То есть, на третий диск мы пишем такие "ключики" :)
Андрей Работает в КАМАЗ
30 ноября, 13:47
ничеси решение! Это вообще уровень не EASY, а EPIC. Наверное EASY, потому что решается в три строчки. Жесть жестяная. Хз как до этого додуматься.
Иван
Уровень 41, Москва
5 сентября, 14:54
Задача решена, спасибо Veryprosto. Но как это работает я хз.
Maks Panteleev Java Developer в Bell Integrator
21 июня, 09:18
мне вот этот видос очень помог разобраться в работе шапочки ^ ))
Андрей Овчаренко
Уровень 41, Москва
10 июня, 15:59
Не делайте так на практике! Результаты замеров на i5-7500 в миллисекундах в цикле от нуля до Integer.MAX_VALUE показывают 183 мс против 2475 мс в пользу человеческого решения с третьей переменной
Тимур
Уровень 37, Рэджо Эмилия, Италия
14 марта, 20:29
alex_us
Уровень 41, Симферополь
28 декабря 2020, 11:50
Пока не оч понимаю как бы я сам догадался до таких алгоритмов..... Гуглежка в помощь
Максим Дудин
Уровень 31, Калининград
19 ноября, 17:35
тоже самое...всё когда объяснили (просто запомнить, что так можно), но как до этого дошел кто-то первый
Андрей
Уровень 38, Москва, Россия
5 октября 2020, 17:50
Через xor решилось легко в 3 строки. Как-то интуитивно, хоть и не очень понятно :)
Евгений Ведущий инженер в ПАО Сбербанк Expert
18 мая 2020, 18:15
Очень интересные возможности предоставляет бинарное счисление. Можно возводить число в степень при помощи << А можно менять примитивы местами без дополнительной переменной😎
Stepan A.
Уровень 37, Сочи, Россия
18 мая 2020, 12:42
Александр
Уровень 40, Екатеринбург
13 июля, 05:36
Спасибо. Хорошее видео.