How to negate base -2 numbers?

Question

I was given a Codility test lately and I was wondering how can I negate -2 base numbers?

For example the array [1,0,0,1,1] represents 9 in base -2:

-2 bases:

1,-2,4,-8,16

1 + (-8) + 16 = 9

[1,0,0,1,1]

Negative 9 in base -2 is:

-2 bases:

1,-2,4,-8

1 + (-2) + -8 = -9

[1,1,0,1]

I'm in the dark regarding the question. There must be some intuitive solution for this. Do you have any hints?

Answer 1

In base −2, a 1 at position i means (−2)ⁱ.

So, a [1,1] in positions [i,i+1] means (−2)ⁱ + (−2)ⁱ⁺¹ = (−2)ⁱ + (−2)(−2)ⁱ = (1 + −2)(−2)ⁱ = −(−2)ⁱ.

So you can negate any occurrence of a [1,0] by changing it to a [1,1], and vice versa.

Any other occurrences of 0, of course, can be left intact: −0 = 0.

So in your example, we split [1,0,0,1,1] into [{1,0}, {0}, {1,1}], negate each part to get [{1,1}, {0}, {1,0}], i.e., [1,1,0,1,0], and remove the unnecessary high 0, producing [1,1,0,1].

Answer 2

Let's try a few examples:

     (16 -8  4 -2  1)
 1 =   0  0  0  0  1
-1 =   0  0  0  1  1
 2 =   0  0  1  1  0
-2 =   0  0  0  1  0
 3 =   0  0  1  1  1
-3 =   0  1  1  0  1
 4 =   0  0  1  0  0
-4 =   0  1  1  0  0
 5 =   0  0  1  0  1
-5 =   0  1  1  1  1

We can try to define this mathematically:

Given input I(b) (where B is the bit number),

1. I = ∑(-2)^bI(b) -- definition of base -2)
2. O = -I -- what we're trying to solve for
3. O = -∑(-2)^bI(b) -- substitution
4. O = ∑-(-2)^bI(b) -- distribution
5. -(-2)^b = (-2)^b + (-2)^b+1
6. O = ∑((-2)^b + (-2)^b+1)I(b) -- substitution
7. O = ∑((-2)^bI(b) + (-2)^b+1I(b)) -- substitution
8. O = ∑(-2)^bI(b) + ∑(-2)^b+1I(b)
9. O(b) = I(b) + I(b-1)

Now, this leaves the possibility that O(b) is 0, 1, or 2, since I(b) is always 0 or 1.

If O(b) is a 2, that is a "carry", Let's look at a few examples of carries:

       (16 -8  4 -2  1)   (16 -8  4 -2  1)
 1+1 =   0  0  0  0  2  =   0  0  1  1  0
-2-2 =   0  0  0  2  0  =   0  1  1  0  0
 4+4 =   0  0  2  0  0  =   1  1  0  0  0

for each b, starting at 0, if O(b) >= 2, subtract 2 from O(b) and increment O(b+1) and O(b+2). Do this until you reach your maximum B.

Hopefully this explains it in enough detail.