Come convertire una base decimale (10) in una base negabinaria (-2)?

Question

Voglio scrivere un programma per convertire da decimale a negabinario.

Non riesco a capire come convertire da decimale a negabinary.

Non ho idea di come trovare la regola e come funziona.

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

So solo che è 7 = (-2)^0*1 + (-2)^1*1 + (-2)^2*0 + (-2)^3*1 + (-2)^4*1.

Answer 1

L'algoritmo è descritto in http://en.wikipedia.org/wiki/Negative_base#Calculation. Fondamentalmente, scegli il resto come caso base positivo e assicurati che il resto sia non negativo e minimo.

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

Solo i miei due centesimi (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

C'è un metodo (attribuito a Librik/Szudzik/Schr ö ppel) che è molto più efficiente:

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

Il metodo di conversione e il suo inverso sono descritti in modo più dettagliato in this answer.