我该如何在C中使用mod 2加法来进行XOR?

问题描述 投票:1回答:2

我读到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. 一次抓取每个字节1位
  2. 在每对位上执行mod 2加法
  3. 将每个结果位存储在输出中
  4. 将输出位返回为1字节
c bit-manipulation bitwise-operators bitwise-xor
2个回答
2
投票

您要在进行模运算之前添加移位的值(在模之前xy应该为0或1)。您应该使用

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

然后添加它们,进行模运算,然后像已经做的那样将位存储到output中。


1
投票

我读到XOR等效于mod 2加法。我的假设虽然是在位级别上。意思是5 XOR 10不等于(5+ 10)mod 2,因为那是5,这是不正确的。

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

按位XOR完全等效于mod 2加法在2阶的循环组中],其中mod 2加法是普通的加法运算符。该组仅具有两个元素,通常标记为0和1。虽然与Modolo 2加成的方式可以直截了当地扩展,但自然不会在与之同构的组上自然定义Modulo 2。巧合的是,按位AND等于对该组元素进行乘法。

考虑到模2加法的结果始终分别为0或1,这取决于加数分别具有相同还是不同的奇偶校验,并且当且仅当1 << c时,认为表达式c具有奇数奇偶校验为零,因此仅当A & (1 << c)为零时,形式为c的表达式才可以具有奇校验(但实际校验也取决于A)。这应该向您显示为什么您的程序无法按预期工作。

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

    x = !(A & (1 << c));
    y = !(B & (1 << c));
    o = (x + y) % 2;
    output |= (o << c);
热门问题
推荐问题
最新问题