[ACCEPTED]-How to convert a decimal base (10) to a negabinary base (-2)?-base-conversion

Score: 13

The algorithm is described in http://en.wikipedia.org/wiki/Negative_base#Calculation. Basically, you 3 just pick the remainder as the positive 2 base case and make sure the remainder is 1 nonnegative 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)
``````
Score: 4
``````def neg2dec(arr):
n = 0
for i, num in enumerate(arr[::-1]):
n+= ((-2)**i)*num
return n

def dec2neg(num):
if num == 0:
digits = ['0']
else:
digits = []
while num != 0:
num, remainder = divmod(num, -2)
if remainder < 0:
num, remainder = num + 1, remainder + 2
digits.append(str(remainder))
return ''.join(digits[::-1])
``````

0

Score: 3

Just 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);
}

return result.ToArray();
}
``````

0

Score: 1

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

``````uint64_t negabinary(int64_t num) {
}
``````

The conversion 2 method and its reverse are described in 1 more detail in this answer.

Score: 0

Here is some code that solves it and display 2 the math behind it. Some code taken from 1 "Birender Singh"

``````#https://onlinegdb.com/xR1E5Cj7L
def neg2dec(arr):
n = 0
for i, num in enumerate(arr[::-1]):
n+= ((-2)**i)*num
return n

def dec2neg(num):
oldNum = num
if num == 0:
digits = ['0']
else:
digits = []
while num != 0:
num, remainder = divmod(num, -10)
if remainder < 0:
num, remainder = num + 1, remainder + 10
print(str(oldNum) + " = " + str(num) + " * -10 + " + str(remainder))
oldNum = num
digits.append(str(remainder))
return ''.join(digits[::-1])

print(dec2neg(-8374932))
``````

Output:

``````-8374932 = 837494 * -10 + 8
837494 = -83749 * -10 + 4
-83749 = 8375 * -10 + 1
8375 = -837 * -10 + 5
-837 = 84 * -10 + 3
84 = -8 * -10 + 4
-8 = 1 * -10 + 2
1 = 0 * -10 + 1
12435148
``````

More Related questions