Problem J
Jumbled Communication
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 XOR1, e.g., $\verb|10110000 ^ 01100100| = \verb|11010100|$. The << operator is a (non-circular) left shift of a byte value2, e.g., $\verb|10111001 << 1| = \verb|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?
Input
The input consists of:
-
one line with an integer $n$ ($1 \le n \le 10^5$), the number of bytes in the message sent by the weather sensor;
-
one line with $n$ integers $b_1, \ldots , b_ n$ ($0 \leq b_ i \leq 255$ for all $i$), the byte values of the message.
Output
Output $n$ byte values (in decimal encoding), the unscrambled message.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 58 89 205 20 198 |
22 55 187 12 66 |
Footnotes
- 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.
- In 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.
