Как я могу создать XOR, используя дополнение 2 мода в C? - PullRequest
Новая
       46

Как я могу создать XOR, используя дополнение 2 мода в C?

1 голос
/ 25 октября 2019

Я читал, что XOR эквивалентно дополнению мода 2. Однако я предполагаю, что это на уровне битов. Значение 5 XOR 10 не равно (5 + 10) mod 2, потому что это будет 1, что неверно. Таким образом, я написал следующую функцию: 

unsigned char XOR_BIT(unsigned char A, unsigned char B)
{
    unsigned char x;
    unsigned char y;
    unsigned char c;
    unsigned char o;
    unsigned char output = 0;
    for(c = 0; c < 8; c++)
    {
        printf("=========Round %u=============\n", c);
        x = (A & (1 << c));
        printf("x: %u\n", x);
        y = (B & (1 << c));
        printf("y: %u\n", y);
        o = (x + y) % 2;
        printf("o: %u\n", o);
        output |= (o << c);
        printf("output: %u\n", output);
    }
    return output;
}

Однако это выдает следующее: 

=========Round 0=============
x: 1
y: 0
o: 1
output: 1
=========Round 1=============
x: 0
y: 2
o: 0
output: 1
=========Round 2=============
x: 4
y: 0
o: 0
output: 1
=========Round 3=============
x: 0
y: 8
o: 0
output: 1
=========Round 4=============
x: 0
y: 0
o: 0
output: 1
=========Round 5=============
x: 0
y: 0
o: 0
output: 1
=========Round 6=============
x: 0
y: 0
o: 0
output: 1
=========Round 7=============
x: 0
y: 0
o: 0
output: 1
MyXOR: 1
Standard XOR: 15

Я подозреваю, что либо неправильно понимаю требуемые побитовые операции, либоошибка кода, но у меня нет достаточных знаний в этой области, чтобы определить проблему.

Предполагаемое поведение этой функции:

  1. Захватить каждый байт 1 бит ввремя
  2. Выполнить сложение по модулю 2 для каждой пары битов
  3. Сохранить каждый результирующий бит на выходе
  4. Вернуть выходные биты как 1 байт

Ответы [ 2 ]

3 голосов
/ 25 октября 2019

Вы добавляете сдвинутые значения перед выполнением по модулю (x и y должны быть либо 0, либо 1 перед модом). Вы должны извлекать биты с помощью 

x = (A >> c) & 1;
y = (B >> c) & 1;

Затем вы добавляете их, выполняете по модулю и сохраняете бит в output, как вы уже делаете.

2 голосов
/ 25 октября 2019

Я читал, что XOR эквивалентно добавлению мода 2. Однако я предполагаю, что это на уровне битов. Это означает, что 5 XOR 10 не равно (5 + 10) mod 2, потому что это будет 5, что неверно.

(5 + 10) mod 2 равно 1, а не 5, но этотакже не тот же результат, что и побитовый xor. Вы более или менее правильно сделали вывод, что утверждение применяется к отдельным битам, но ваш код предполагает, что вы, возможно, не полностью поняли это.

Побитовое XOR полностью эквивалентно добавлению мода 2 в циклическую группупорядка 2 , для которого добавление мода 2 является обычным оператором сложения. Эта группа имеет только два элемента, условно обозначенные 0 и 1. Добавление по модулю 2 не определено естественным образом для групп, не гомоморфных этому, хотя оно может быть расширено прямым способом. По совпадению, побитовое И эквивалентно умножению на элементы этой группы.

Учтите, что результатом сложения по модулю 2 всегда является либо 0, либо 1, в зависимости от того, имеют ли адденды одинаковую или разную четность соответственнои учтите, что выражение 1 << c имеет нечетную четность тогда и только тогда, когда c равно нулю, поэтому выражения вида A & (1 << c) могут иметь нечетную четность только тогда, когда c равно нулю (но фактическая четность зависит также отA). Это должно показать вам, почему ваша программа не работает так, как вы ожидаете.

Вам необходимо сопоставить свои x и y с 0 и 1, чтобы выполнить вычисления. Есть несколько способов сделать это. Наиболее очевидный способ - выполнить побитовые сдвиги, как это уже описано в другом ответе. Для ваших конкретных целей вы также можете использовать двойное логическое отрицание, что в некоторых отношениях даже более естественно. А из-за симметрии задачи вы можете даже упростить это до одного отрицания: 

    x = !(A & (1 << c));
    y = !(B & (1 << c));
    o = (x + y) % 2;
    output |= (o << c);
...