Can a series of XORs be undone?

Question

I have run a couple tests on paper but cant seem to find a confirmation anywhere.

Say I have several unique 8 bit numbers and I XOR them together and store that somewhere. If I then, later, xor those same numbers together with that stored number will I always get 0?

Basically I have an enumeration of conditions, some of which need to be fulfilled before an operation can occur. As a sanity check, and to make sure I dont accidentally come back and break this code later, I was considering XORing the needed conditions together to begin, then as the conditions are met XORing the condition with that stored value. Then right before the operation occurs, making sure that we are back to 0.

So something like

sanity_check = C1 ^ C3 ^ C5
...
//Condition one is met
sanity_check ^= C1
...
//Condition 3 is met
sanity_check ^= C3
...
//Condition 5 is met
sanity_check ^= C5
...
if( sanity_check == 0 )
 Do operation

I know it is not flawless because with the right conditions I could end up with an intermediate 0 state in there somewhere. But it is more for my own use as a guard against accidentally moving one of those conditions below the operation in the future.

Answer 1

Yes, XOR is commutative and associative, and x ^ x == 0, so you can undo a sequence of XORs by doing the same sequence again.

Answer 2

It would be better to use a bit field, where each bit represents a condition:

C1 = 1;  // 1 << 0
C2 = 2;  // 1 << 1
C3 = 4;  // 1 << 2
C4 = 8;  // 1 << 3
C5 = 16; // 1 << 4

// Condition one is met
sanity_check |= C1;

....

// If Conditions 1 2 and 4 passed
if((sanity_check & (C1 | C2 | C4)) == (C1 | C2 | C4))

// If Conditions 1 and 2 passed and 3 failed
if((sanity_check & (C1 | C2 | C3)) == (C1 | C2))

This way you can check for different condition sets using bitwise operators when you get to the point in your code where you want to check them. You also are guaranteed that the if statement will only be entered if all your requirements are met (rather than the possibility of a false positive).

Answer 3

Yes. Daniel's answer provides a nice basis for understanding intuitively why XOR's are perfectly reversible. I get the sense that you want to sure that this is always the case. Time to head down the rabbit hole!

Binary numbers (which are what ints and everything else boil down to) along with the ^ operator form something called a group. This means that for ints a, b and c.

1. a ^ b is always also an int.
2. a ^ b ^ c is always the same, no matter pair you calculate first. This is what Daniel meant by "associative".
3. There is an int (0) for which 0 ^ a = a ^ 0 = a. This is the identity, in that XORing 0 with an int does not change it.
4. For any a you choose, there is always, always, always b so that a ^ b = b ^ a = 0. In such a situation, b is called the inverse of a in that it neutralizes a to give the identity. You can also prove that there is only one such inverse for every number, but I'm not going to do that.

Now, the particular pair of ints and ^ has two more properties that make what you say possible.

1. a ^ b == b ^ a for any a & b. This is what Daniel meant by "commutative".
2. a ^ a = 0, which means that an int is it's own inverse with respect to ^.

Using this, let's take your expression as an example. The final result you get after all your operations is:

C1 ^ C3 ^ C5 ^ C1 ^ C3 ^ C5

Now, because we have commutativity, we can switch them around and pair them up to get:

C1 ^ C1 ^ C3 ^ C3 ^ C5 ^ C5

And because of associativity and the self inverse thing, we get:

(C1 ^ C1) ^ (C3 ^ C3) ^ (C5 ^ C5) = 0 ^ 0 ^ 0 = 0

You can use the same logic to reassure yourself with any expression. This will always be true. The fact that you get an intermediate 0 does not matter. Indeed it does not matter what any of the values are. Math's got you covered.