Вопрос:

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

c# algorithm

4053 просмотра

7 ответа

10450 Репутация автора

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

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

Автор: l--''''''---------'''''''''''' Источник Размещён: 13.10.2010 07:58

Ответы (7)


6 плюса

104773 Репутация автора

В Википедии есть отличное объяснение алгоритма 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 )НЕ будет делать то, что подразумевает имя метода (оно обнуляет значение , по факту).

Автор: LBushkin Размещён: 13.10.2010 08:02

5 плюса

198920 Репутация автора

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

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

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

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

Автор: jason Размещён: 13.10.2010 08:05

1 плюс

4574 Репутация автора

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

Автор: UGEEN Размещён: 13.10.2010 08:28

7 плюса

32738 Репутация автора

Решение

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

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

Автор: Rafał Dowgird Размещён: 13.10.2010 09:00

1 плюс

433 Репутация автора

Прежде всего посмотрите, как работает 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 входа различаются, что именно то, что нам нужно.

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

Автор: gilligan Размещён: 13.10.2010 09:02

2 плюса

21 Репутация автора

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

Автор: Krunch Размещён: 13.10.2010 09:18

0 плюса

17 Репутация автора

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

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

Я надеюсь, что это помогает.

Автор: Mani Kandan Размещён: 13.06.2019 05:43
Вопросы из категории :
32x32