Your best friend Adam has recently bought a Raspberry Pi and some equipment, including a wireless temperature sensor and a 433MHz receiver to receive the signals the sensors sends. Adam plans to use the Raspberry Pi as an in-door display for his weather sensor. As he is very good with electronics, he quickly managed to get the receiver to receive the signals of the sensor. How-ever, when he looked at the bytes sent by the sensor he could not make heads or tails of them. After some hours looking through a lot of websites, he found a document explaining that his weather sensor scrambles the data it sends, to prevent it from being used together with products from other manufacturers.
Luckily, the document also describes how the sensor scrambles its communication. The document states that the sensor applies the expression
x ^ (x << 1) to every byte sent. The
^ operator is bit-wise XOR 1, e.g., 10110000 ^ 01100100 = 11010100. The
<< operator is a (non-circular) left shift of a byte value 2, e.g., 10111001 << 1 = 01110010.
In order for Adam’s Raspberry Pi to correctly interpret the bytes sent by the weather sensor, the transmission needs to be unscrambled. However, Adam is not good at programming (actually he is a pretty bad programmer). So he asked you to help him and as a good friend, you are always happy to oblige. Can you help Adam by implementing the unscrambling algorithm?
The input consists of:
one line with an integer n (1 ≤ n ≤ 105), the number of bytes in the message sent by the weather sensor;
one line with n integers b1,… , bn (0 ≤ bi ≤ 255 for all i), the byte values of the message.
Output n byte values (in decimal encoding), the unscrambled message.
5 58 89 205 20 198
22 55 187 12 66
1: In bit-wise XOR, the i-th bit of the result is 1 if and only if exactly one of the two arguments has the i-th bit set.
x << j, the bits of x are moved j steps to the left. The j most significant bits of x are discarded, and j zeroes are added as the least significant bits of the result.
This NWERC 2015 problem is licensed under the CC BY-SA 3.0 license.
You can find the original problem on the NWERC website.