1x10 ^ 49 in decimale - come bit binario è quello e come si dovrebbe convertirlo in binario?

Question

ho incontrato un sito web che utilizza un 50 cifre decimali ID intero in una stringa di query URL, che sembra un po 'eccessivo.

Il più piccolo numero decimale 50 cifre è 1.0 x 10^49, altrimenti noto come:

1000000000
0000000000
0000000000
0000000000
0000000000

1. Quanti bit sarebbe la rappresentazione binaria contenere?
2. Come ci si avvicina la conversione di un numero così elevato decimale a binario, prendendo in considerazione il limite del campo di senza segno a 32 bit interi o 64 bit interi?

Chiedo fuori solo per curiosità programmatore puro - non si tratta di una domanda di università, problemi di lavoro o intervista di puzzle

!

Answer 1

1. 49 * log (10) / log (2) = 162,774,477 mila, pertanto la rappresentazione binaria conterrebbe 163 bit.

2. Utilizzare una classe bigint e applicare il standard di algoritmo per la conversione da decimale a binario.

Answer 2

La rappresentazione binaria minimo (con precisione intero) può essere trovata prendendo il registro (base 2) del numero. In questo caso la quantità minima di bit binari sarebbe log (10 ^ 49) = 162,77. Abbiamo bisogno di un numero intero quindi ci limiteremo a chiamarlo 163 bit.

Se dovessi rappresentare quel numero, e la precisione in una rappresentazione in virgola mobile era insufficiente, vorrei solo uso di alcune BigInteger biblioteca.

Answer 3

Poiché ogni cifra decimale trasmette le stesse informazioni come bit lb 10, qualsiasi numero 50 cifre si inserisce in bit ceil(lb(10)*50) = 167.

In particolare, non è così difficile convertire da decimale a binario, anche a mano. Basta dividere per due, e mettere il modulo (1 se l'ultima cifra era strano, 0 se anche) alla fine del vostro risultato binario. Se avete bisogno di tali numeri ad alto contenuto di un programma, basta usare l'esecuzione intero grande della vostra piattaforma, per esempio BigInteger in Java e solo int in pitone. In assenza di questo, per cercare una biblioteca numerica.

Oh, e 10 ^ 49 in binario è 163 po 'lungo:

110
1101 0111 1001 1111 1000 0010 0011 0010
1000 1110 1010 0011 1101 1010 0110 0001
1110 0000 0110 0110 1110 1011 1011 0010
1111 1000 1000 1010 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000

Answer 4

Si potrebbe utilizzare un adeguato libreria di manipolazione LongInteger per la conversione di tali numeri. Se non è consentito utilizzare la lettura del sorgente può dare conoscenze utili su come queste cose vengono fatte in modo efficiente.

Per quanto riguarda il numero di bit è sufficiente per risolvere l'equazione:

2 ^N = 10 ⁵⁰

prendere un log ₂ di entrambe le parti:

N = log ₂ 10 ⁵⁰

Ora convertire log ₂ per accedere ₁₀ :

N = log ₂ 10 ⁵⁰ = log ₁₀ 10 ⁵⁰ / log ₁₀ 2 = 50 / log ₁₀ 2

Prendere il numero intero successivo (ceil) di N -. Che è il numero di bit necessari

Answer 5

1) 2 ^ 10 ~ 10 ^ 3 in modo 10 ^ 48 ~ 2 ^ 160; 10 ^ 49 sarà quantità 164 bit.

2) Utilizzare una classe BigInteger o MPI (di cui ci sono molte cose da trovare se la libreria API standard lingua non viene con uno). Knuth ha i dettagli.

Answer 6

mi piacerebbe utilizzare un linguaggio di alto livello che gestisce grandi numeri interi per me. Esempio IRB (Ruby) sessione:

>> (10**49).to_s
=> "10000000000000000000000000000000000000000000000000"
>> (10**49).to_s(2)
=> "1101101011110011111100000100011001010001110101000111101101001100001111000000110011011101011101100101111100010001010000000000000000000000000000000000000000000000000"
>> (10**49).to_s(2).size
=> 163

Answer 7

Che cosa si intende esattamente per la memorizzazione di un numero X?

1. Vuoi dire la memorizzazione di tutti i numeri compresi tra 0 e X?
2. o tutti i numeri tra -X e X?
3. memorizzazione o solo le informazioni:. Null / X

La mia sensazione è che l'intervistatore avrebbe potuto significare il terzo. La risposta sarebbe 1 bit.

Answer 8

50 cifre decimali interi vanno da 10 ^ 49-10 ^ 50-1. 10 ^ 49 è 163 bit, e 10 ^ 50-1 è 167 bit. Se si desidera che il numero esatto di bit, è necessario prendere il logaritmo di quei grandi numeri direttamente, piuttosto che semplicemente calcolando la "scorciatoia" 50 * log ₁₀ (2).

In alternativa, è possibile convertire il numero in binario utilizzando un convertitore decimale-binario precisione arbitraria e contare i bit (BTW, il convertitore ho collegato a conta i bit per voi).