На нашем сайте мы используем cookie для сбора информации технического характера и обрабатываем IP-адрес вашего местоположения. Продолжая использовать этот сайт, вы даете согласие на использование файлов cookies. Здесь вы можете узнать, как мы пользуемся файлами cookies.
Я согласен
логотип upread.ru

Алгоритм XOR-обмена на C#


Алгоритм XOR-обмена дает возможность для обмена значениями двух целочисленных переменных, не требуя использования третьей, временной переменной. Этот алгоритм интересно знать, хотя его использование не обязательно в языках высокого уровня.

Замена двух значений

Это обычная задача - поменять местами значения, содержащиеся в двух переменных, например, при сортировке данных с помощью алгоритма пузырьковой сортировки. Самый простой способ добиться этого - использовать третью, временную переменную. Код метода, выполняющего такой своп, показан ниже. В этом случае два обмениваемых значения называются "a" и "b", а временная переменная - "c". Метод показан как статический, так что его можно вызвать из метода Maun консольного приложения.

static void Swap(ref int a, ref int b)
{
    int c = a;
    a = b;
    c = a;
}
При разработке на языках низкого уровня, особенно на ассемблере, а также при наличии небольшого числа регистров или ограниченной памяти использование временной переменной может быть ограничено. В этих случаях вы можете использовать алгоритм XOR-обмена для переключения значений в двух местах без необходимости какого-либо временного хранения. Хотя это имеет ограниченное применение и, возможно, неэффективно для языков высокого уровня, интересно понять, как работает алгоритм.

Алгоритм

Алгоритм XOR-обмена использует побитовые исключающие операции ИЛИ (XOR) для обмена двух числовых значений. Три операции XOR выполняются с использованием двух переменных. Три функции для переменных с именами A и B:

A = A XOR B
B = B XOR A
A = A XOR B
Этот, казалось бы, простой процесс можно показать используя следующую таблицу. Каждая строка в таблице показывает стадию процесса, а первая строка - начальное состояние. Столбцы A и B показывают значения переменных A и B на каждом этапе процесса. В последних двух строках уравнения упрощаются, когда одно и то же значение присутствует дважды. Это возможно, потому что XOR двух совпадающих значений всегда равен нулю. Столбцы a и b показывают примеры значений для A и B в десятичном и двоичном виде.



Реализация алгоритма XOR-обмена на C#

Мы можем очень легко реализовать алгоритм XOR-обмена, используя логические побитовые операторы C# и составное присваивание. Способ достижения этого показан ниже. Обратите внимание, что первый оператор проверяет, равны ли эти два значения. Это решает проблему, заключающуюся в том, что если две переменные используют одну и ту же ссылку, то алгоритм потерпит неудачу. Это происходит потому, что первый XOR обнуляет оба значения.

static void XorSwap(ref int a, ref int b)
{
    если (a != b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }
}
Чтобы протестировать этот метод, мы можем добавить следующий код к основному методу программы. Это меняет местами два значения и выводит их начальное и конечное значения. Попробуйте изменить значения и выполнить программу несколько раз, чтобы увидеть результаты.

int a = 88;
int b = 12;
 
Console.WriteLine("a = {0}, b = {1}", a, b);
XorSwap(ref a, ref b);
Console.WriteLine("a = {0}, b = {1}", a, b);
 
/* Выведет на консоль
 
a = 88, b = 12
a = 12, b = 88
 
*/




Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.



тегизаметки, си шарп, алгоритмы

Читайте также:




Замена задачи с сохранением конечного результата
Состояния потоков и планирование их выполнения


© upread.ru 2013-2021
При перепечатке активная ссылка на сайт обязательна.
Задать вопрос
письмо
Здравствуйте! Вы можете задать мне любой вопрос. Если не получается отправить сообщение через эту форму, то пишите на почу up777up@yandex.ru
Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.