How to convert decimal base (10) to negative base (-2)?

Question

I want to write a program to convert from decimal to negabinary.

I cannot figure out how to convert from decimal to negabinary.

I do not know how to find the rule and how it works.

Example: 7(base10)-->11011(base-2)

I just know that this is 7 = (-2)^0*1 + (-2)^1*1 + (-2)^2*0 + (-2)^3*1 + (-2)^4*1 .

Answer 1

The algorithm is described at http://en.wikipedia.org/wiki/Negative_base#Calculation . Basically, you simply select the remainder as the positive base case and make sure that the remainder is non-negative and minimal.

  7 = -3*-2 + 1 (least significant digit) -3 = 2*-2 + 1 2 = -1*-2 + 0 -1 = 1*-2 + 1 1 = 0*-2 + 1 (most significant digit) 

Answer 2

Only my two cents (C #):

 public static int[] negaBynary(int value) { List<int> result = new List<int> (); while (value != 0) { int remainder = value % -2; value = value / -2; if (remainder < 0) { remainder += 2; value += 1; } Console.WriteLine (remainder); result.Add(remainder); } return result.ToArray(); } 

Answer 3

There is a method (attributed to Librik / Szudzik / Schr & ouml; ppel) that is much more efficient:

 uint64_t negabinary(int64_t num) { const uint64_t mask = 0xAAAAAAAAAAAAAAAA; return (mask + num) ^ mask; } 

The conversion method and its inverse are described in more detail in this answer .