Binary to Decimal

Q: Qual è la complessità temporale della conversione da binario a decimale?

Entrambi i cicli visitano ciascuno degli n caratteri una volta, quindi richiedono un tempo O(n) . Mantengono solo uno o due numeri, quindi usano uno spazio extra O(1) . Per una stringa di 31 caratteri, sono 31 passaggi.

Q: Riesci a convertire un numero binario in decimale usando gli shift dei bit?

Sì. value << 1 raddoppia il valore e | digit imposta il bit meno significativo, quindi value = (value << 1) | digit fa la stessa cosa di value * 2 + digit . La forma con lo shift chiarisce che stai spostando i bit, mentre la forma aritmetica funziona anche per basi diverse da 2.

PrincipianteMatematica e simulazione Manipolazione dei bit

+10

Ricevi una stringa s che rappresenta un numero non negativo in binario, usando solo i caratteri 0 e 1. Restituisci il valore di quel numero come numero intero ordinario. La stringa non ha zeri iniziali, tranne nel caso del numero zero, che è rappresentato dal singolo carattere 0.

Funzione

toDecimal(s: string) → integer

sstring: le cifre binarie del numero
Restituisceinteger: il valore di s come numero intero

Vincoli

1 ≤ s.length ≤ 31
s contiene solo 0 e 1.
s inizia con 1, a meno che s non sia "0".
Leggi le cifre da solo invece di chiamare una conversione di base integrata.

Esempi

Input: s = "1101"
Output: 13
Spiegazione: Leggendo da destra, le posizioni valgono 1, 2, 4 e 8. 1101 ha 1 nelle posizioni di 8, 4 e 1, e 8 + 4 + 1 = 13.

Input: s = "0"
Output: 0
Spiegazione: Un singolo 0 non ha 1 in nessuna posizione, quindi il suo valore è 0.

Input: s = "10000000"
Output: 128
Spiegazione: L’unico 1 ha sette 0 alla sua destra, quindi si trova nella posizione che vale 2^7 = 128.

+16 test nascosti all’invio

Per approfondire

Riesci a leggere un numero scritto in una qualsiasi base da 2 a 16 con lo stesso ciclo, in cui le lettere a fino a f rappresentano le cifre da 10 a 15?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni cifra binaria rappresenta una potenza di due, determinata dalla distanza dall’estremità destra. Puoi sommare quelle potenze partendo da destra oppure leggere la stringa da sinistra e raddoppiare il valore a ogni passaggio. Il ciclo di raddoppio non calcola mai una potenza ed è lo stesso ciclo che usi per leggere un testo decimale, con 2 al posto di 10.

Aggiungi i valori posizionali da destra

Intuizione

La cifra più a destra vale 1, la successiva 2, poi 4, 8 e così via, raddoppiando a ogni passo verso sinistra. Il numero è la somma dei valori posizionali che corrispondono a un 1. Quindi procedi dall'ultimo carattere al primo, mantieni il valore posizionale corrente in power e aggiungilo ogni volta che la cifra è 1.

Per 1101 incontri 1 (aggiungi 1), 0 (salta 2), 1 (aggiungi 4) e 1 (aggiungi 8), per un totale di 13. Ogni cifra viene visitata una volta, quindi il ciclo richiede O(n) tempo e due numeri di memoria.

Fai attenzione alla dimensione di power. Per una stringa di 31 cifre raggiunge 2^30 all'ultima cifra e viene poi raddoppiato un'altra volta fino a 2^31, che non rientra in un intero con segno a 32 bit. Mantieni power in una variabile a 64 bit oppure interrompi i raddoppi dopo l'ultima cifra.

Algoritmo

Imposta total = 0 e power = 1.
Scorri la stringa dall'ultimo carattere al primo.
Se il carattere è 1, aggiungi power a total.
Raddoppia power prima di spostarti di una posizione a sinistra.
Restituisci total.

def toDecimal(s):
    total = 0
    power = 1  # the place value of the rightmost digit
    for i in range(len(s) - 1, -1, -1):
        if s[i] == "1":
            total += power
        power *= 2
    return total

Raddoppia e somma da sinistra

Intuizione

Leggi la stringa da sinistra e mantieni value, il numero rappresentato dalle cifre lette finora. Aggiungere un’altra cifra binaria sposta ogni cifra precedente di una posizione a sinistra, raddoppiandone il valore, e poi aggiunge la nuova cifra. Quindi, a ogni passaggio, si esegue value = value * 2 + digit.

Per 1101, value assume i valori 1, poi 1 * 2 + 1 = 3, poi 3 * 2 + 0 = 6, poi 6 * 2 + 1 = 13. Ogni prefisso della stringa è un numero binario più piccolo, e il ciclo mantiene esattamente quel numero, quindi dopo l’ultima cifra contiene il valore completo.

Il valore non supera mai la risposta finale, quindi per una stringa di 31 cifre rimane entro 2^31-1 e basta un intero a 32 bit. La cifra è il codice del carattere meno il codice di '0', che trasforma '1' in 1 e '0' in 0. Questo è il metodo standard per analizzare un numero da un testo in qualsiasi base.

Algoritmo

Imposta value = 0.
Per ogni carattere da sinistra a destra, trasformalo in una cifra sottraendo il codice di '0'.
Imposta value = value * 2 + digit.
Restituisci value.

def toDecimal(s):
    value = 0
    for ch in s:
        # Shift the digits read so far one place left, then add the new one.
        value = value * 2 + (ord(ch) - ord("0"))
    return value

Trappole e casi limite

La maggior parte delle risposte sbagliate dipende dalla direzione della scansione o dal tipo della cifra.

Assegnare alla cifra più a sinistra il valore posizionale 1. I valori posizionali partono dall'estremità destra, quindi scorri a partire dall'ultimo carattere oppure usa il ciclo di raddoppio da sinistra.
Sommare il carattere invece della cifra. In molti linguaggi '1' è il numero 49, quindi value * 2 + '1' è molto più grande del dovuto. Sottrai prima '0'.
Far traboccare il valore posizionale. Raddoppiare power dopo la 31ª cifra dà 2^31, che va in overflow o causa un arresto anomalo con un intero a 32 bit.
Calcolare ciascun valore posizionale con una funzione di potenza in virgola mobile. In C, C++ e Java, pow(2, k) restituisce un double, e il risultato deve essere riconvertito in un intero.

Domande frequenti4

Come si converte il binario in decimale?

Assegna a ogni cifra un valore posizionale: 1 per quella più a destra, poi 2, 4, 8 e così via verso sinistra. Somma i valori posizionali delle cifre che sono 1. Per 1101 è 8 + 4 + 1 = 13.

Perché raddoppiare il valore funziona?

Scrivere un’altra cifra alla fine di un numero binario sposta ogni cifra precedente di una posizione a sinistra, e ogni posizione vale il doppio di quella alla sua destra. Quindi il vecchio valore raddoppia e la nuova cifra aggiunge 0 oppure 1. Ripetendo questo procedimento dalla prima cifra all’ultima si costruisce il numero intero.

Qual è la complessità temporale della conversione da binario a decimale?

Entrambi i cicli visitano ciascuno degli n caratteri una volta, quindi richiedono un tempo O(n). Mantengono solo uno o due numeri, quindi usano uno spazio extra O(1). Per una stringa di 31 caratteri, sono 31 passaggi.

Riesci a convertire un numero binario in decimale usando gli shift dei bit?

Sì. value << 1 raddoppia il valore e | digit imposta il bit meno significativo, quindi value = (value << 1) | digit fa la stessa cosa di value * 2 + digit. La forma con lo shift chiarisce che stai spostando i bit, mentre la forma aritmetica funziona anche per basi diverse da 2.

Python

def toDecimal(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "1101"

Atteso