CODEWITHSUNDEEP
cbit-manipulationbitwise-operatorsbitwise-xor
the_endian
the_endian

Reputation: 2527

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

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 1 which is incorrect. Thus, I've written the following function:

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;
}

However, this outputs the following:

=========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

I suspect that I am either misunderstanding the bitwise operations required, or I have a code bug but I don't quite have the necessary knowledge in this domain to determine the problem.

The intended behavior of this function is:

  1. Grab each byte 1 bit at a time
  2. Perform mod 2 addition on each pair of bits
  3. Store each result bit in the output
  4. Return the output bits as 1 byte

Upvotes: 1

Views: 1617

Answers (2)

John Bollinger
John Bollinger

Reputation: 180113

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 is 1, not 5, but this also is not the same result as the bitwise xor. You have inferred more or less correctly that the assertion applies to individual bits, but your code suggests that you may not have fully understood that.

Bitwise XOR is fully equivalent to mod 2 addition in the cyclic group of order 2, for which mod 2 addition is the ordinary addition operator. This group has only two elements, conventionally labeled 0 and 1. Modulo 2 addition is not naturally defined on groups that are not homomorphous to that, though it can be extended in a straightforward way. Coincidentally, bitwise AND is equivalent to multiplication over the elements of this group.

Consider that the result of a modulo 2 addition is always either 0 or 1, depending on whether the addends have the same or different parity, respectively, and consider that the expression 1 << c has odd parity if and only if c is zero, so that expressions of the form A & (1 << c) can have odd parity only when c is zero (but the actual parity depends also on A). This should show you why your program is not working as you expect.

You need to map your x and y to 0 and 1 in order to perform your computation. There are several ways to do this. The most obvious way is to perform bitwise shifts, such as another answer already describes. For your particular purposes, you can also use double logical negation, which in some ways is even more natural. And because of the symmetry of the problem, you can even simplify that to single negation:

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

Upvotes: 2

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

You're adding shifted values before doing the modulo (x and y should be either 0 or 1 before the mod). You should be extracting the bits with

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

Then you add them, do the modulo, and store the bit into output like you already are doing.

Upvotes: 3

Related Questions