USACO February 2006 Problem 'neg2' Analysis

by Bruce Merry

While it is possible work out the bits from left to right, it is easier to work from right to left. If x is odd then the last bit (in base -2) is a 1, otherwise it is a 0. Furthermore, removing the last bit leaves behind either -x/2 or (-x+1)/2 (depending on the parity of x). If we apply the same process to this number, we will get the second-last digit and so on. The process can be summarised in the following algorithm:

while x is not zero:
    if x is odd:
        prepend '1' to answer
        x := x - 1
    else:
        prepend '0' to answer
    x := x / -2

Belarus's Aleksey Ropan submitted a solution that does exactly that:

var
    a:array[1..10000]of integer;
    k,i,n:longint;
begin
    assign(input,'neg2.in'); reset(input);
    assign(output,'neg2.out'); rewrite(output);
    read(n);
    k:=0;
    repeat
        inc(k);
        a[k]:=abs(n mod 2);
        n:=-trunc((n-a[k])/ 2);
    until n=0;
    for i:=k downto 1 do write(a[i]);
    writeln;
    close(output);
end.