Decimal to Binary

Q: Riesci a convertire in binario con operazioni bit a bit invece che con la divisione?

Sì. n & 1 restituisce il bit meno significativo e n >> 1 lo elimina, che equivale a n % 2 e n / 2 per i numeri non negativi. Il ciclo e l’inversione restano uguali. La divisione è più facile da spiegare, mentre la versione con lo shift è comune nel codice di basso livello.

PrincipianteMatematica e simulazione Manipolazione dei bit

+10

Ti viene dato un intero non negativo n. Restituisci la sua rappresentazione binaria come stringa di 0 e 1, senza zeri iniziali. L’unico numero la cui risposta inizia con 0 è zero stesso, che si scrive "0".

Funzione

toBinary(n: integer) → string

ninteger: il numero da convertire
Restituiscestring: le cifre binarie di n come stringa

Vincoli

0 ≤ n ≤ 2³¹-1
Costruisci tu la stringa invece di chiamare una funzione integrata di conversione della base.

Esempi

Input: n = 13
Output: "1101"
Spiegazione: 13 = 8 + 4 + 1. Le posizioni di 8, 4, 2 e 1 contengono 1, 1, 0 e 1, che si legge 1101.

Input: n = 0
Output: "0"
Spiegazione: Zero non ha bit impostati, ma la risposta deve comunque contenere una cifra, quindi è "0" anziché una stringa vuota.

Input: n = 64
Output: "1000000"
Spiegazione: 64 è 2^6, un singolo 1 nella posizione delle 64 seguito da sei 0 per le posizioni da 32 fino a 1.

+16 test nascosti all’invio

Per approfondire

Riesci a convertire n in una base qualsiasi da 2 a 16 usando lo stesso ciclo, impiegando le lettere da a a f per le cifre superiori a 9?

Suggerimenti

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

0 di 3 aperti

Soluzione

Un numero binario è una somma di potenze di due e ogni cifra indica se una potenza è inclusa nella somma. Puoi determinare le cifre dall’alto sottraendo le potenze di due, oppure leggerle dal basso come resti di divisioni ripetute per 2. Il ciclo di divisione è il metodo standard: non è mai necessario trovare prima la potenza più grande e funziona allo stesso modo per ogni base.

Sottrai le potenze di due dall’alto

Intuizione

Ecco come convertire a mano. Trova la massima potenza di due che rientra in n; questa è la prima cifra, un 1. Poi scendi di una potenza alla volta. Se la potenza rientra ancora in ciò che resta, scrivi 1 e sottraila; altrimenti scrivi 0.

Per 13 la potenza massima è 8. Scrivi 1 e tieni 5. Poi 4 ci sta (1, tieni 1), 2 non ci sta (0) e 1 ci sta (1). Le cifre lette sono 1101. La prima cifra è sempre un 1, quindi non possono esserci zeri iniziali.

Trovare la massima potenza richiede attenzione. Raddoppiare power finché supera n causa un overflow di un intero a 32 bit quando n ≥ 2^30, perché la potenza successiva è 2^31. Raddoppiare solo finché power ≤ n / 2 si ferma alla potenza corretta senza mai superare n. Un numero a 31 bit richiede 31 passaggi, ovvero O(log n).

Algoritmo

Se n è 0, restituisci "0".
Imposta power a 1 e raddoppialo mentre power ≤ n / 2.
Mentre power > 0: se n ≥ power, aggiungi 1 e sottrai power da n; altrimenti aggiungi 0.
Dimezza power e ripeti.
Restituisci le cifre che hai aggiunto.

def toBinary(n):
    if n == 0:
        return "0"
    # Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
    power = 1
    while power <= n // 2:
        power *= 2
    bits = []
    while power > 0:
        if n >= power:
            bits.append("1")
            n -= power
        else:
            bits.append("0")
        power //= 2
    return "".join(bits)

Divisione ripetuta per 2

Intuizione

L'ultima cifra binaria di n indica se n è dispari, ed è n % 2. Dividere per 2 e scartare il resto sposta ogni cifra di una posizione a destra, quindi la cifra successiva diventa l'ultima. Ripeti finché non rimane più nulla e raccogli tutte le cifre, dalla più piccola alla più grande.

Per 13: 13 dà resto 1, 6 dà 0, 3 dà 1 e 1 dà 1; poi il numero è 0. I resti, nell'ordine, sono 1, 0, 1, 1; al contrario si leggono 1101. Il ciclo si interrompe quando il numero raggiunge 0, quindi la cifra più significativa che scrive è sempre un 1 e non compare alcuno zero iniziale. Lo zero non entra mai nel ciclo, perciò ha bisogno di un controllo specifico.

A ogni passaggio il numero viene dimezzato, quindi un valore a 31 bit richiede 31 passaggi, un tempo O(log n) e la stringa di cifre occupa uno spazio O(log n).

Algoritmo

Se n è 0, restituisci "0".
Mentre n > 0, aggiungi n % 2 come cifra e imposta n a n / 2, arrotondato per difetto.
Inverti le cifre, perché sono uscite dalla meno significativa alla più significativa.
Restituiscile come stringa.

def toBinary(n):
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        # The remainder is the lowest bit that is left.
        bits.append(str(n % 2))
        n //= 2
    # The bits came out lowest first, so turn them around.
    bits.reverse()
    return "".join(bits)

Trappole e casi limite

Il ciclo è breve e la maggior parte delle risposte errate riguarda i suoi due estremi.

Restituire una stringa vuota per 0. Il ciclo di divisione non viene mai eseguito per zero, quindi controllalo per primo.
Dimenticare di invertire. I resti arrivano a partire dalla cifra meno significativa, quindi 6 diventa 011 invece di 110.
Usare / in un linguaggio in cui restituisce una frazione, come JavaScript, Lua o PHP. 13 / 2 deve diventare 6, quindi arrotonda per difetto o usa la divisione intera.
Costruire la potenza più grande raddoppiando oltre n. Per n = 2^31-1, la potenza successiva, 2^31, non entra in un intero a 32 bit.
Allocare troppo poco spazio in C. Un numero a 31 bit richiede 31 caratteri più il terminatore '\0'.

Domande frequenti4

Come si converte un numero decimale in binario?

Dividi il numero per 2 più volte, annotando ogni resto, finché il numero non raggiunge 0. Leggi i resti dall’ultimo al primo. Per 13 i resti sono 1, 0, 1, 1, quindi 13 in binario è 1101.

Perché i resti si leggono in ordine inverso?

La prima divisione per 2 ti dice se il numero è dispari, ovvero qual è l'ultima cifra binaria. Ogni divisione successiva rivela la cifra seguente a sinistra. Quindi i resti vengono fuori partendo dalla cifra meno significativa e li inverti per scrivere il numero nel modo consueto.

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

Ogni passaggio dimezza il numero, quindi il ciclo viene eseguito una volta per cifra binaria, cioè circa log2(n) volte. Questo richiede un tempo O(log n), e la stringa della risposta occupa uno spazio O(log n). Per un intero a 32 bit, sono al massimo 31 passaggi.

Riesci a convertire in binario con operazioni bit a bit invece che con la divisione?

Sì. n & 1 restituisce il bit meno significativo e n >> 1 lo elimina, che equivale a n % 2 e n / 2 per i numeri non negativi. Il ciclo e l’inversione restano uguali. La divisione è più facile da spiegare, mentre la versione con lo shift è comune nel codice di basso livello.

Python

def toBinary(n):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

n = 13

Atteso

"1101"