Internet Problem Solving Contest

• Correct output – I1
• Correct output – I2
• An interpreter used to test your solutions

Easy data set

Consider first the simpler problem: To increment a number in register A by one. In general such a number has binary representation x01ⁿ, where x is an arbitrary string of ones and zeroes and notation d^k means k consecutive digits d (so 1ⁿ is n ones). Clearly by incrementing this number by one, we get x10ⁿ.

In order to perform this operation on our machine we first separate the rightmost (least significant) block of n ones. We do this in the following way:

First we negate the number to get y10ⁿ (where y is a bitwise negation of x).

Then we replace y by ones. We can do this by propagating that rightmost one to the left by shl-ing and or-ing similar to this:

After this block we have something like y′110ⁿ in register B (where y′ is some string of ones and zeroes). Clearly by repeating this block (at least) 64 times we can get 1^64-n0ⁿ in register B. But that will make out program too long. Fortunately we now have (at least) two rightmost ones so we can go faster:

and we get y′′11110ⁿ. Now we have four ones so we can go even faster. Another four blocks will complete the work:

Now we have 1^64-n0ⁿ in B. That is what we wanted the rightmost ones (in original number) are separated. Some simple operations will finish the incrementation:

Clear out the rightmost ones in A to get x00ⁿ,

construct the one on n + 1-th place (0^63-n10ⁿ),

and put that one into A.

And we are done. Almost. Our task was to increment value in A by 8, not 1. However since binary representation of 8 is 1000 the solution is similar. We just shift the number to the right by 3 positions, add 1 and shift it back (while preserving last 3 bits). Sure you can imagine how to do that.

Also note that the above construction of incrementing by one need not work if the result would overflow. However in order to use it to solve our origonal task this is not important since we shift the inpit number to the right (so result of incrementation will not overflow) and then we shift it left (so excess bits will get lost).

Hard data set

First let’s find out how does next permutation of bit sequence look like. Clearly a next permutation of a sequence x011^m0ⁿ is x100ⁿ1^m. That is, to get a next permutation we find the rightmost one preceded by a zero, move it one place to the left and push the block of ones right of it far to the right. If there is no one preceded by a zero, then the input is either 0 or its next permutation does not fit in 64-bit register.

In order to find the next permutation we separate the blocks of n zeroes and m ones by using the similar method as in solution of easy task:

Now we have 1^k111^m0ⁿ in B (where k = 62 - n - m) and to separate m ones we do

to get y100^m0ⁿ in C (where y is a bitwise negation of x) and

to get 1^k100^m0ⁿ in C. Now we can clear out the rightmost m ones in A

and find the one that was originaly the rightmost one preceded by zero and move it one place to the left (it is the rightmost one of C).

Now we have x100^m+n in A and 0^k100^n+m in D. Using the current values on B,C and D we can reconstruct the block of m ones:

Now we have 0^k001^m0ⁿ in D. All we need is to push them n places to the right. We can do this with the help of value in B. First we negate it to get 0^64-n1ⁿ

and then we will simultaneously shift B and D while there ar som ones in B. This can be done in the following way:

First we check if there is a one in B:

Now E is 0 if B has no ones and E is 1 if there are some ones in B. This works because B has form 0^64-n1ⁿ. So we can shift B and D by E.

So by these two blocks we can shift D by one place to the right and clear one one from B if there is one. By repeating them (at least) 64 times we can shift D to the right by n places because B originally contained n ones. However this would (probably) make the program too long. Of course we can go faster, for example:

This will shift D by 8 places to the right and clear 8 ones from B if there are at least 8 of them. By using 7 blocks similar to above one we can shift D to the right by n places in a more efficient way:

And all that remains is ti put those shifted m ones into A

and we are done.