Find an algorithm for writing any positive integer in negabinary, i.e., as a sum of powers of 2.
For example,
7 = 11011 = (2)^4 + (2)^3 + (2)^1 + (2)^0
19 = 10111 = (2)^4 + (2)^2 + (2)^1 + (2)^0
the algorithm works the same as it does for binary except with a little twist.
Digits are limited to {0,1} just like with binary.
To convert a base 10 number like 10 to binary you keep dividing by 2 and keeping track of the remainders.
10/2 = 5 rem 0
5/2 = 2 rem 1
2/2= 1 rem 0
1/2=0 rem 1
then you read off the remainders in reverse order to get the digits, which in this case would be 1010. We can verify that 2^3+2^1=10
Now for NegaBinary we divide by 2 instead of 2. Calculating the dividend and remainder is little bit trickier because we are dividing by a negative number. For binary what we are actually doing is trying to find a,b such that a*2+b=n with b restricted to {0,1}. For NegaBinary it is the same except 2 is replaced by 2. b is easy to find as it is simply n mod 2, then a is simply (nb)/(2). Thus for finding the NegaBinary digits of 10 we have
10/(2) = 5 rem 0
(5)/(2) = 3 rem 1
3/(2) = 1 rem 1
(1)/(2) = 1 rem 1
1/(2) = 0 rem 1
thus the digits are 11110 and we can verify that
(2)^4+(2)^3+(2)^2+(2)^1=168+42=10.
The proof that this representation is unique is left as an exercise for the reader ;)

Posted by Daniel
on 20130814 21:20:31 