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),

  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.

Tags:

Java

Math