4
$\begingroup$

I found in Wikipedia that you can convert base 10 to a negative base simple by dividing to a base and keeping remainder like this:
enter image description here

Source: http://en.wikipedia.org/wiki/Negative_base

Now I'm stuck here.

I want to convert two digits -6 and 6 no base(-2)

Now example:

I do this:

6 / -2 = -3, remainder 1
-3/ -2 = 1, remainder 1
1/ -2 = 0, remainder 0

so, the final result is 0011 which is not quite right, because 1x(-2) + 1 = -1, not six.

HELP!

Update:

And one more question concerning negabinary:

Suppose we use 2n bits to represent integers using base −2 encoding, for n > 0. What is the largest integer we can represent? What is the smallest?

What I'm thinking is that the smallest number is 0, because we cannot represent -1 in negative numbers of bits. 2x(-1) = -2. ANd there's no limit to a max number since 2x(10000) will fit in 200000 bytes.

1 Answers 1

6

6/-2=-3 with remainder 0, not 1

-3/-2=2 with remainder 1 (remember that your remainders have to be positive, like the -5/-3 in the example)

2/-2=-1 with remainder 0

-1/-2=1 with remainder 1

1/-2=0 with remainder 1

giving $11010_{-2}=6_{10}$

For your question about largest and smallest numbers representable in $2n$ bits, the largest positive number has all the positive bits set, so you have $1+4+16+\ldots$ This is $\sum_{i=0}^{n-1}4^i=\frac{4^n-1}{3}$. The smallest number has all the negative bits set and is twice this large in absolute value, so it is $-\frac{2(4^n-1)}{3}$

  • 1
    Oh, right. I should round them. -3/-2 = 1.5 => 2. Great. Any suggestion on the second question?2011-09-11
  • 2
    It is not rounding, it is the ceiling function for negative bases, floor function for positive bases. That makes sure the remainder is positive.2011-09-11
  • 0
    This works great. The only question I have is the last question. I do not quite understand why negative bits set is twice this large in absolute value. Can you please explain this to me a little more? I would appreciate that.2011-09-13
  • 1
    @user194076: the place values are 1, -2, 4, -8, ... So each negative value place is twice the previous positive value place in absolute value. As you specified 2n bits, we will end with a negative value place. And we don't need a sign bit.2011-09-13
  • 0
    Okay. I got this part. Now I have a problem understanding (4n-1)/3 Why do we divide by three and why it is 4n-1. I feel so stupid :(2011-09-13
  • 1
    @user194076: The sum is a geometric series as each term is a fixed multiple (here 4) of the preceding. The formula for its sum is given in http://en.wikipedia.org/wiki/Geometric_series2011-09-13
  • 0
    OOOH! Right-right. I completely forgot math. Gotta go back to high school. Thanks a lot!2011-09-13