C # используя побитовый XOR для замены

Question

void swap(ref int x, ref int y)
{       x = x ^ y;   y = y ^ x;   x = x ^ y;  }

я узнаю о побитовом XOR.как происходит этот обмен?это поражает меня.этот метод должен поменять местами содержимое X и Y, но я совсем не понимаю, что происходит?

Answer 1

Осторожно. Этот метод имеет очень очень неприятное свойство. Он использовался в одной из записей Подфаншированного С контеста. Это будет работать счастливо ... пока однажды кто-то не попробует что-то вроде замены двух элементов массива a [i] и a [j], не гарантируя, что i! = J.

Когда обе ссылки ссылаются на одну и ту же переменную, этот метод обнуляет ее.

Answer 2

В Википедии есть отличное объяснение алгоритма Swap-By-XOR .

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

Но в упрощенном виде мы можем считать каждый бит двоичного значения отдельным, поскольку операция XOR действует для каждого независимо. Таким образом, достаточно показать, что это работает с 1-битными значениями, поскольку по индукции мы можем продемонстрировать, что это работает для любого двоичного значения длины. Довольно просто построить соответствующую таблицу истинности для этих операций, поэтому я опускаю это.

Swap by XOR - не единственный «творческий» алгоритм обмена. Аналогичного результата можно добиться с помощью арифметических операций:

void Swap( ref int x, ref int y )
{
  x = x + y; 
  y = x - y;
  x = x - y; 
}

С практической точки зрения эту технику следует избегать в большинстве случаев. Как вы сами понимаете, логика этого метода не сразу очевидна и может привести к проблемам с удобством обслуживания и расширяемости. ... не в последнюю очередь это тот факт, что Swap( ref x, ref x ) НЕ будет делать то, что подразумевает название метода (фактически, оно обнулит значение).

Answer 3

Просто посмотрите на него один бит за раз и один шаг за один раз.

x|y -> x = x ^ y x|y -> y = y ^ x x|y -> x = x ^ x x|y
0|0              0|0              0|0              0|0
0|1              1|1              1|0              1|0
1|0              1|0              1|1              0|1
1|1              0|1              0|1              1|1

Здесь вы можете ясно видеть, что результатом в каждом случае является замена битов.Отсюда понятно, почему это работает в общем случае.Возможны более формальные объяснения.

Каждый раз, когда вы говорите: «Я вообще не понимаю, что происходит», это убедительный признак того, что вы должны найти более четкий способ семантической записи-эквивалентный код.

Answer 4

swap () может быть реализован с помощью одной инструкции CPU на большинстве современных архитектур (включая i686 и x86_64).Следовательно, вам лучше написать его таким образом, чтобы компилятор мог распознавать и преобразовывать его соответствующим образом, а не пытаться микрооптимизировать таким образом, чтобы фактически сделать ваш код медленнее и менее читабельным.

Answer 5

Прежде всего посмотрите, как работает XOR:

a | b | a^b
- - - - - -
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 0

Таким образом, результат операции xor равен 1 или true, если входы различны, и 0, если входы равны. Еще один способ взглянуть на него - думать о нем как о добавлении без переноса, я обозначу его как (+):

x = x ^ y <=> x = x (+) y;
y = y ^ x <=> y = y (+) x;
x = x ^ y <=> x = x (+) y;

Первый шаг : установите все биты, которые равны 0 в x, но 1 в y, в 1. Теперь некоторые биты неверны в x, потому что если бит равен 1 в x, а также y, то это будет установить в 0. Остальные биты верны.

Второй шаг : Теперь установите те же битовые позиции, которые мы установили от 1 в x до 0 в y (мы покончили с y сейчас). Это работает, потому что x уже имеет все биты, отличающиеся от 1, поэтому XOR y с x теперь в основном означает: переключать биты в y, которые установлены на 1 в x. Мы с тобой закончили:)

Третий шаг : теперь нам все еще нужно установить те биты в x в 1, которые уже были изначально установлены в 1 и были сброшены в 0 после первого шага обратно в 1. Как? Мы просто XOR x с y в последний раз, потому что что делает xor? он устанавливает бит в 1, если 2 входа различаются, а это именно то, что нам нужно.

Если вы все еще не уверены в этом, вы должны просто нарисовать это на бумаге и просмотреть, как это работает, и / или обратиться к таблицам, которые Джейсон делал выше.

Answer 6

Обмен XOR интересен - но с другой стороны - действительно ли он более эффективен, чем обмен по временному члену?Компилятор обычно оптимизирует код в таких случаях.

Answer 7

поменяйте местами два числа с помощью побитового оператора: используйте следующий PYTHON код:

m,n=map(int,input().split())
m=m^n
n=m^n
m=m^n
print(m,n)

Надеюсь, это поможет.