How to convert a decimal base (10) to a negabinary 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 have no idea about how to find the rule and how it works.

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

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

Have you seen http://en.wikipedia.org/wiki/Negative_base#Calculation? — kennytm, Feb 17 '12 at 15:33

score 13 · Accepted Answer · edited Jan 11 '16 at 23:39

13

The algorithm is described in http://en.wikipedia.org/wiki/Negative_base#Calculation. Basically, you just pick the remainder as the positive base case and make sure the remainder is 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)

edited Jan 11 '16 at 23:39

Mateusz Piotrowski

8,029
10
53
79

answered Feb 17 '12 at 17:17

kennytm

510,854
105
1,084
1,005

score 3 · Answer 2 · answered Jun 02 '19 at 15:52

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

score 2 · Answer 3 · answered Jan 11 '16 at 23:01

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);
        result.Add(remainder);
    }

    return result.ToArray();
}

score 1 · Answer 4 · edited May 23 '17 at 12:07

1

There is a method (attributed to Librik/Szudzik/Schrö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 reverse are described in more detail in this answer.

edited May 23 '17 at 12:07

Community

1
1

answered Jun 07 '16 at 05:00

m69's been on strike for years

11,835
3
34
57

score 0 · Answer 5 · answered Sep 13 '22 at 18:37

Here is some code that solves it and display the math behind it. Some code taken from "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

How to convert a decimal base (10) to a negabinary base (-2)?

5 Answers5

Linked