我如何在 C 中使用 mod 2 加法来制作 XOR？

Question

我读到 XOR 等同于 mod 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 位
对每对位执行mod 2加法
将每个结果位存储在输出中
Return 输出位为 1 个字节

Answer 1

您在执行 modulo 之前添加移位值（x 和 y 在 mod 之前应该是 0 或 1）。您应该使用

提取位

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

然后添加它们，执行 modulo，然后将位存储到 output 中，就像您已经在做的那样。

Answer 2

I read that XOR is equivalent to mod 2 addition. My assumption though is that this is at the bit level. Meaning, 5 XOR 10 is not equal to (5 + 10) mod 2, because that would be 5 which is incorrect.

(5 + 10) mod 2 是 1，不是 5，但这也与按位异或的结果不同。您或多或少正确地推断出该断言适用于各个位，但您的代码表明您可能没有完全理解这一点。

按位异或完全等价于2阶循环群中的mod2加法，其中mod2加法是普通加法运算符.这个群只有两个元素，通常标记为 0 和 1。模 2 加法自然不会定义在与其同态的群上，尽管它可以直接扩展。巧合的是，按位 AND 相当于对这个组的元素进行乘法运算。

考虑 modulo 2 加法的结果总是 0 或 1，这取决于加数分别具有相同还是不同的奇偶校验，并考虑表达式 1 << c当且仅当 c 为零时具有奇校验，因此只有当 c 为零时 A & (1 << c) 形式的表达式才能具有奇校验（但实际奇偶校验还取决于 A).这应该会告诉您为什么您的程序没有按预期运行。

您需要将 x 和 y 映射到 0 和 1 才能执行计算。有几种方法可以做到这一点。最明显的方法是执行位移位，例如已经描述的另一个答案。对于您的特定目的，您还可以使用双重逻辑否定，这在某些方面更为自然。由于问题的对称性，您甚至可以将其简化为单一否定：

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

我如何在 C 中使用 mod 2 加法来制作 XOR？

How can I craft XOR Using mod 2 addition in C?

c

bit-manipulation

bitwise-operators

bitwise-xor