Binary number with base $-2$ (minus two) arithmetic algorithm

Question

I have a number X represented as a sequence of $a_i \in {0,1}$ so $$X = \sum_{i=0}^{N-1} a_i(-2)^i$$ where $N \in \{ 1, \ldots, 100000 \}$.

I need to find an algorithm to produce a number $Y = -X$ that is not based on calculating of X because it can be extremely high. In addition it should be of O(N) complexity.

For example:

-1 = 11,   1 = 1
-2 = 10,   2 = 110
-3 = 1101, 3 = 111
-4 = 1100, 4 = 100
-5 = 1111, 5 = 101
-6 = 1110, 6 = 11010
-7 = 1001, 7 = 11011
-8 = 1000, 8 = 11000
-9 = 1011, 9 = 11001

I can not apply binary arithmetic here, but I feel that the problem can be solved using bit shifting. Please help me with the algorithm or math methods which can help.

Answer 1

For a given $X$ the left shift will give $X' = -2*X$.

To calculate $Y=-X$ we can write $Y=X'+X$.

The above addition can be done by converting them to decimal easily.

Adding these numbers in base $-2$ is tricky since they do not follow binary rules of addition. So the addition can be done by using following rules:

1. $0+0=0$
2. $0+1=1$
3. $1+0=1$
4. $1+1=110$
5. $11+1=0$

Using the above rules the value of $Y=X'+X$ can be obtained.

Answer 2

Lets call $X^{ls}$ your number with its bits shifted one place to th left: $$X^{ls} = \sum_{i=1}^{N} a_{i-1}(-2)^i = \sum_{i=0}^{N-1} -2 a_i(-2)^i=-2X$$

So $$-X = X^{ls} + X$$