Алгоритм 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
 
*/