Bit Count in MalnarScript

You are required to output a valid MalnarScript program that computes a number from the binary representation of its input. In this problem, the input is a single nonnegative integer a satisfying (0 \le a < 2^n). For this problem, assume (n=4) and the program may contain at most (k=1) command. In MalnarScript there is only one unsigned 4-bit variable named a, which initially holds the input value and whose final value is taken as the output.

Each command in MalnarScript must be of the form:

a =

where the expression () is defined recursively as follows:

[ \texttt{ = a ;|; ;|; () } ]

Here, () represents any nonnegative decimal integer strictly less than (2^4 = 16); and () can be one of the following: +, -, |, &, <<, or >>. In any given expression, the variable a may appear at most 5 times. All addition and subtraction operations are performed modulo (2^4=16).

Your task is to output (from your own program) a MalnarScript program that computes the number of 1’s in the binary representation of its input. A correct MalnarScript solution for (n=4) is given by a single command that sets a to the sum of the bits of a. For example, the following command computes the bit count of a 4‐bit number:

[ a = ((a & 1) + (((a >> 1) & 1) + (((a >> 2) & 1) + ((a >> 3) & 1)))) ]

When this MalnarScript program is executed, it will replace every occurrence of a in the right‐hand side with the current value of a, evaluate the parenthesized expressions, and then update a. The final value of a (i.e. the number of 1’s in the binary representation of the input) is then output.

Your program (written in your chosen language) should simply print the above MalnarScript program exactly, regardless of its own input.

inputFormat

A single nonnegative integer a such that (0 \le a < 16). This integer will be provided as input to the MalnarScript program you output.

outputFormat

A single nonnegative integer representing the number of 1's in the binary representation of the input. Note that your program should output a MalnarScript program which, when run, performs this computation.

sample

5

a = ((a & 1) + (((a >> 1) & 1) + (((a >> 2) & 1) + ((a >> 3) & 1))))