Come convertire una base decimale (10) ad una base negabinary (-2)?
-
27-10-2019 - |
Domanda
Voglio scrivere un programma per convertire da decimale a negabinary.
Non riesco a capire come convertire da decimale a negabinary.
Non ho idea su come trovare la regola e come funziona.
Esempio: 7(base10)-->11011(base-2)
Ho appena so che è 7 = (-2)^0*1 + (-2)^1*1 + (-2)^2*0 + (-2)^3*1 + (-2)^4*1
.
Soluzione
L'algoritmo è descritto in http://en.wikipedia.org/wiki/Negative_base#Calculation . In pratica, basta scegliere il resto come il caso base positiva e assicurarsi che il resto è non negativo e minimale.
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)
Altri suggerimenti
Proprio 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();
}
C'è un metodo (attribuito a Librik / Szudzik / Schröppel) che è molto più efficace:
uint64_t negabinary(int64_t num) {
const uint64_t mask = 0xAAAAAAAAAAAAAAAA;
return (mask + num) ^ mask;
}
Il metodo di conversione e la sua inversa sono descritti in maggior dettaglio nel questa risposta .
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])