1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ Edited. Thank you @RossMillikan. $\endgroup$ – N74 Dec 16 '15 at 17:41
  • $\begingroup$ Thank you for suggestion. As long as can't calculate X could you please advice a method of calculating addition of two numbers with base -2? $\endgroup$ – Oleg Kubrakov Dec 17 '15 at 4:22
  • $\begingroup$ It's a singular base you have, if you don't want to make groupings on the digits (as @Daga suggests) you can use a positive and a negative carry. The negative carry arises when you sum two ones (or a one and a positive carry). The positive carry arises when you sum two zeros and a negative carry. $\endgroup$ – N74 Dec 17 '15 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.