# Multiple XOR operations

Find $$8$$ distinct $$8$$-bit numbers, each with $$4$$ bits set to one, such that the cumulative XOR of these bytes is $$10101010$$.

I imagine there are multiple answers, so the first correct answer wins the prestigious check mark.

For non-mathmo's,

• $$0 \operatorname{XOR} 0=0$$
• $$0 \operatorname{XOR} 1 = 1$$
• $$1 \operatorname{XOR} 0 = 1$$
• $$1 \operatorname{XOR} 1 = 0$$

$$\operatorname{XOR}$$ is commutative, and therefore the question wants an even number of bits set in columns that result in $$0$$, and an odd number of bits set in columns that result in a $$1$$.

For example,

1 1 0 0
0 1 1 0
0 0 1 1
-------
1 0 0 1

• When first reading "4 bit set" I was thinking of a set of 4 bits. I suggested an edit – melfnt Feb 10 at 10:32

One solution:

 Number    Cumulative
11110000  11110000
00111100  11001100
00001111  11000011
11101000  00101011
11000011  11101000
00101101  11000101
11000101  00000000
10101010  10101010

Strategy:

1) Try to reach 0 after 7 numbers. That way, number 8 is simply the final number.

2) To reach 0 after 7 numbers, I make sure that at each step up to step 6, my cumulative value has 4 bits. Then, number 7 will be the cumulative value, to erase all 4 bits and leave 0.

3) To maintain 4 bits, at each step I erase 2 existing bits and set 2 new bits. I just need to make sure not to repeat any numbers, by using a new pair of bits each time.

If there are 8 numbers with 4 ones in each, there must be 32 ones in total. You can do it like this:

11110000
01111000
00111100
00011110
00001111
10000111
11000011
11100001

The XOR of these 8 will be 00000000, but we can easily fix it by switching around some bits of the 2nd number:

11110000
11010010
00111100
00011110
00001111
10000111
11000011
11100001

Note that switching around entire odd/even-numbered columns also works (odd with odd, even with even).

• your solution is better than mine – melfnt Feb 11 at 7:12

This will do it:

1 1 0 0 1 1 0 0
1 1 0 1 1 0 0 0
1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 0
1 1 1 0 0 0 1 0
0 0 1 1 0 0 1 1
1 0 1 1 0 0 1 0
0 0 1 0 0 1 1 1

• Boo! I will have it known that I got there ahead of JS1 by thirteen whole seconds. (Seriously, of course it's fine that JS1 got the coveted green checkmark -- their answer offers a specific strategy and mine doesn't -- because my approach was very ad hoc and it didn't seem worth trying to describe what was in my head as I did it.) – Gareth McCaughan Feb 10 at 10:55

Another solution (ninjaed):

1- 11110000
2- 01111000
3- 00111100
4- 00011110
5- 00001111

6- 10010110
7- 00110011

8- 10101010

Strategy (not so illuminating nor useful I think):

I wrote down numbers 1 to 5 by shifting a 4-bit block of consecutive ones - there is no particular reason to do it, I just did so to write down 5 different numbers out of 8 quickly. Then I used number 6 and 7 to cancel the cumulative xor so that number 8 can just be the required solution.

1 0 1 0 1 0 1 0
0 1 1 0 1 0 1 0
0 0 1 1 1 0 1 0
0 1 0 1 1 0 1 0
1 0 0 0 1 0 1 1
1 1 0 0 0 0 1 1
0 0 1 1 0 0 1 1
0 1 1 1 0 0 0 1
---------------
1 0 1 0 1 0 1 0