How to negate base -2 numbers?
In base −2, a 1 at position i means (−2)i.
So, a [1,1] in positions [i,i+1] means (−2)i + (−2)i+1 = (−2)i + (−2)(−2)i = (1 + −2)(−2)i = −(−2)i.
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].
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),
- I = ∑(-2)bI(b) -- definition of base -2)
- O = -I -- what we're trying to solve for
- O = -∑(-2)bI(b) -- substitution
- O = ∑-(-2)bI(b) -- distribution
- -(-2)b = (-2)b + (-2)b+1
- O = ∑((-2)b + (-2)b+1)I(b) -- substitution
- O = ∑((-2)bI(b) + (-2)b+1I(b)) -- substitution
- O = ∑(-2)bI(b) + ∑(-2)b+1I(b)
- 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.