The wannabe scientist Kleofáš has recently developed a new processor. The processor has got 26 registers, labeled A to Z. Each register is a 64-bit unsigned integer variable.
This new processor is incredibly simple. It only supports the instructions specified in the table below. (In all instructions, R is a name of a register, and X is either the name of a register, or a 64-bit unsigned integer constant.)
| syntax | semantics |
|---|---|
| mov R X | Store the value X into R. |
| and R X | Compute the bitwise and of the values R and X, and store it in R. |
| or R X | Compute the bitwise or of the values R and X, and store it in R. |
| xor R X | Compute the bitwise xor of the values R and X, and store it in R. |
| not R | Compute the bitwise not of the value R, and store it in R. |
| shl R X | Take the value in R, shift it to the left by X bits, and store the result in R. |
| shr R X | Take the value in R, shift it to the right by X bits, and store the result in R. |
Notes:
Example task:
Assume that the register A contains an arbitrary input number between 0 and 15, and that all the other registers contain zeroes. Write a program that will set Z to 1 if the number of set bits in A is odd, and to 0 otherwise.
Solution for the example task:
The answer can easily be computed as the bitwise xor of the four lowest bits in A.
We can isolate a single bit X by first shifting the number 63 - X bits to the left (the X-th bit will become the most significant one, and all more significant bits of A become lost), and then 63 bits to the right (the originally X-th bit is now the least significant one).
In this way we can take the four bits of A that may be non-zero, and store them into B to E, respectively. We then compute the bitwise xor of these four bits and store it in Z.
| The entire program solving the example task:
mov B A
shl B 63 shr B 63 mov C A shl C 62 shr C 63 mov D A shl D 61 shr D 63 mov E A shl E 60 shr E 63 mov Z B xor Z C xor Z D xor Z E |
Easy task:
Assume that the register A contains an arbitrary input number, and that all the other registers contain zeroes. Write a program that will increase the value in A by 8 (computing modulo 264, if necessary). After your program terminates, the other registers are allowed to contain anything. Your program must have less than 64 instructions.
Hard task:
Assume that the register A contains an arbitrary input number, and that all the other registers contain zeroes. Write a program that will change the value in register A into the next larger value with the same number of set bits. After your program terminates, the other registers are allowed to contain anything. Your program must have less than 300 instructions.
In other words, if we regard A as a sequence of 0s and 1s, your task is to produce the next permutation of the given sequence.
For example, if the input is 23, which is 10111 in binary, the output should be 27, which is 11011 in binary. If the input is 24, which is 011000 in binary, the output should be 33, which is 100001.
You may assume that the output for the given number in A is always less than 264. I.e., the input will be such that the next larger value with the same number of set bits still fits into the 64-bit register.
Input specification
This problem has no input.
Output specification
Send us your program as a text file. Each line of the file may either contain one complete instruction, or just whitespace.