1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ When first reading "4 bit set" I was thinking of a set of 4 bits. I suggested an edit $\endgroup$ – melfnt Feb 10 at 10:32
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ your solution is better than mine $\endgroup$ – melfnt Feb 11 at 7:12
2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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.) $\endgroup$ – Gareth McCaughan Feb 10 at 10:55
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.