void swap(ref int x, ref int y)
{ x = x^y; y = y^x; x = x^y; }
im узнать о побитом XOR. как происходит это обмен? это дует мне в голову. этот метод должен поменять содержимое X и Y, но я не понимаю ВСЕГО, что происходит?C# с использованием побитового XOR для замены
Остерегайтесь. Этот метод имеет очень очень неприятное свойство. Он использовался в одной из записей Underhanded C Contest. Он будет работать с удовольствием ... до тех пор, пока кто-то не попытается что-то вроде обмена двумя элементами массива: [i] и [j], не гарантируя, что i! = J.
Если обе ссылки относятся к одной и той же переменной, этот метод обнуляет ее.
Вы верны в принцип. 'Swap (ref x, ref x)' будет обнулять переменные 'x'. В C/C++ этот подход имеет недостаток, который вы описываете. Однако в C# невозможно передать элементы массива с помощью ref, чтобы конкретный случай не мог произойти. – LBushkin
@LBushkin: Я считаю, что вы ошибаетесь. То, что вы не можете передать по ссылке, - это вывод индексатора, поэтому 'swap (ref a [0], ref a [0])' не будет компилироваться, если 'a' является' List', но будет (и будет выполняться), если это массив ints. –
Действительно, вы правы. Виноват. – LBushkin
Википедия имеет отличное объяснение Swap-By-XOR algorithm.
Формальное доказательство того, что этот алгоритм работает, немного связано и требует использования математических свойств двоичных чисел.
Но в упрощенной форме мы можем рассматривать каждый бит двоичного значения отдельно, поскольку операция 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) НЕ будет делать то, что подразумевает название метода (он будет обнулять значение, фактически).
Просто взгляните на него один бит за раз и один шаг за раз.
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
Здесь вы можете четко видеть, что результатом в каждом случае является замена битов. Отсюда понятно, почему он работает в общем случае. Подробнее formal объяснения возможны.
В любое время, когда вы говорите: «Я совсем не понимаю, что происходит», является убедительным доказательством того, что вы должны найти более четкий способ написания семантически эквивалентного кода.
У вас есть опечатка, последний шаг x = x^y; но записи в таблице, конечно, правильные .. :) – gilligan
XOR swaping интересен - но с другой стороны - это действительно эффективнее, чем замена временного члена? Компилятор обычно оптимизирует код в таких случаях.
Память мудрая, она более эффективна, так как она на месте, а временная переменная - нет. Не говоря о том, что это достаточно, чтобы использовать его, но на некоторых устройствах это может быть очень хорошо (больше кода выполняется во встроенных системах, чем на ПК, верьте или нет. Большинство из них написано не на C# :)) –
Прежде всего рассмотрим, как работает XOR:
a | b | a^b
- - - - - -
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 0
Таким образом, результат операции исключающего является 1 или верно, если входы различны, и 0, если входы равны. Другой способ смотреть на него, чтобы думать о нем, как дополнение без переноса, я буду обозначать как (+):
x = x^y <=> x = x (+) y;
y = y^x <=> y = y (+) x;
x = x^y <=> x = x (+) y;
Первый шаг: установить все биты, которые 0 в х, но 1 в y до 1.Теперь некоторые биты ошибочны в x, потому что если бит равен 1 в x, а также y, он будет равен 0. Другие биты верны.
Второй шаг: Теперь установите одинаковые позиции бит, которые мы установили в 1 по x на 0 в y (мы закончили с y сейчас). Это работает, потому что x уже имеет все биты, которые отличаются от 1, поэтому XORing y с x теперь в основном означает: переключение битов в y, которые установлены в 1 в x. Мы закончили с y сейчас :)
Третий шаг: теперь нам по-прежнему необходимо установить эти биты в x в 1, которые уже были установлены в 1 изначально, и были сброшены на 0 после первого шага назад до 1. Как ? Мы просто XOR x с y в последний раз, потому что то, что делает xor? он устанавливает бит в 1, если два входа различаются, что именно то, что нам нужно.
Если вы все еще смущены, вы должны просто нарисовать его на бумаге и воспроизвести, чтобы увидеть, как это работает и/или обратиться к таблицам, которые сделал Джейсон выше.
swap() может быть реализован с помощью одной команды процессора на большинстве современных архитектур (включая i686 и x86_64). Следовательно, вам лучше писать его таким образом, чтобы компилятор мог распознавать и преобразовывать соответственно, а не пытаться микро-оптимизировать таким образом, чтобы на самом деле сделать ваш код более медленным и менее читаемым.
Запишите операции на бумаге с примерами значений x и y в двоичном формате. – Oded
Держите его таким образом и не используйте его. Кто-нибудь будет поддерживать ваш код в один прекрасный день. Вы найдете несколько потоков под тегом C++, посмотрите на нисходящие. В противном случае напишите его с 0 и 1, чтобы увидеть, как он работает. Достаточно двух бит. –
Это был один из меняющихся трюков, который я узнал в первом классе compsci, который я взял для удовольствия. Я не мог не чувствовать себя глупо, выполняя эту микро микро оптимизацию без каких-либо оснований, тогда как очевидная альтернатива (temp = x; x = y; y = temp;) в миллион раз яснее. И, вероятно, в миллион раз легче оптимизировать компилятор. – Joren