Binary to Decimal

Q: Quelle est la complexité temporelle de la conversion du binaire en décimal ?

Les deux boucles parcourent chacun des n caractères une fois, donc elles prennent un temps de O(n) . Elles ne conservent qu’un ou deux nombres, ce qui représente un espace supplémentaire de O(1) . Pour une chaîne de 31 caractères, cela fait 31 étapes.

Q: Peux-tu convertir le binaire en décimal à l’aide de décalages de bits ?

Oui. value << 1 double la valeur et | digit définit le bit de poids faible, donc value = (value << 1) | digit fait la même chose que value * 2 + digit . La forme avec décalage montre clairement que tu déplaces des bits, tandis que la forme arithmétique fonctionne aussi pour les bases autres que 2.

DébutantMaths et simulation Manipulation de bits

+10

Vous obtenez une chaîne s qui écrit un nombre non négatif en binaire, en utilisant uniquement les caractères 0 et 1. Renvoyez la valeur de ce nombre sous forme d’entier ordinaire. La chaîne ne comporte pas de zéros en tête, sauf pour le nombre zéro, qui est représenté par le caractère unique 0.

Fonction

toDecimal(s: string) → integer

sstring: les chiffres binaires du nombre
Renvoieinteger: la valeur de s en tant qu’entier

Contraintes

1 ≤ s.length ≤ 31
s ne contient que 0 et 1.
s commence par 1, sauf si s est "0".
Lisez vous-même les chiffres au lieu d’appeler une conversion de base intégrée.

Exemples

Entrée: s = "1101"
Sortie: 13
Explication: En partant de la droite, les positions valent 1, 2, 4 et 8. 1101 a des 1 aux positions correspondant à 8, 4 et 1, et 8 + 4 + 1 = 13.

Entrée: s = "0"
Sortie: 0
Explication: Un seul 0 n’a de 1 à aucune position, donc sa valeur est 0.

Entrée: s = "10000000"
Sortie: 128
Explication: Le seul 1 a sept 0 à sa droite, donc il se trouve à la position qui vaut 2^7 = 128.

+16 tests cachés à la soumission

Pour aller plus loin

Peux-tu lire un nombre écrit dans n’importe quelle base de 2 à 16 avec la même boucle, où les lettres a à f représentent les chiffres de 10 à 15 ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque chiffre binaire représente une puissance de deux, déterminée par sa distance par rapport à l’extrémité droite. Tu peux additionner ces puissances en partant de la droite, ou lire la chaîne de gauche à droite et doubler la valeur à chaque étape. La boucle de doublement ne calcule jamais de puissance et c’est la même boucle que celle utilisée pour lire un texte décimal, avec 2 à la place de 10.

Ajouter les valeurs de position en partant de la droite

Intuition

Le chiffre le plus à droite vaut 1, celui qui le précède vaut 2, puis 4, 8, et ainsi de suite, en doublant à chaque pas vers la gauche. Le nombre est la somme des valeurs de position correspondant à un 1. Parcourez donc les caractères du dernier au premier, conservez la valeur de position actuelle dans power, et ajoutez-la chaque fois que le chiffre est 1.

Pour 1101, vous rencontrez 1 (ajoutez 1), 0 (ignorez 2), 1 (ajoutez 4) et 1 (ajoutez 8), ce qui donne 13. Chaque chiffre est parcouru une fois, donc la boucle prend un temps de O(n) et utilise deux nombres en mémoire.

Surveillez la taille de power. Pour une chaîne de 31 chiffres, elle atteint 2^30 au dernier chiffre, puis est encore doublée pour atteindre 2^31, ce qui ne tient pas dans un entier signé de 32 bits. Stockez power dans une variable de 64 bits, ou arrêtez de le doubler après le dernier chiffre.

Algorithme

Définissez total = 0 et power = 1.
Parcourez la chaîne de son dernier caractère jusqu’au premier.
Si le caractère est 1, ajoutez power à total.
Doublez power avant de vous déplacer d’une position vers la gauche.
Retournez 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

Multiplier par 2 et additionner à partir de la gauche

Intuition

Lisez la chaîne de gauche à droite et conservez value, le nombre représenté par les chiffres lus jusque-là. Ajouter un chiffre binaire décale chaque chiffre précédent d’une position vers la gauche, ce qui double sa valeur, puis ajoute le nouveau chiffre. Chaque étape consiste donc à effectuer value = value * 2 + digit.

Pour 1101, value vaut 1, puis 1 * 2 + 1 = 3, puis 3 * 2 + 0 = 6, puis 6 * 2 + 1 = 13. Chaque préfixe de la chaîne est un nombre binaire plus petit, et la boucle conserve exactement ce nombre ; après le dernier chiffre, elle contient donc la valeur entière.

La valeur ne dépasse jamais le résultat final, donc pour une chaîne de 31 chiffres, elle reste inférieure ou égale à 2^31-1 et un entier de 32 bits suffit. Le chiffre correspond au code du caractère moins le code de '0', ce qui transforme '1' en 1 et '0' en 0. C’est la méthode standard pour analyser un nombre à partir d’un texte dans n’importe quelle base.

Algorithme

Définis value = 0.
Pour chaque caractère, de gauche à droite, transforme-le en chiffre en soustrayant le code de '0'.
Définis value = value * 2 + digit.
Retourne 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

Pièges et cas limites

La plupart des réponses incorrectes sont dues au sens du parcours ou au type du chiffre.

Attribuer la valeur de position 1 au chiffre le plus à gauche. Les valeurs de position commencent à l’extrémité droite : parcours donc la chaîne depuis le dernier caractère, ou utilise la boucle de doublement depuis la gauche.
Ajouter le caractère au lieu du chiffre. Dans de nombreux langages, '1' correspond au nombre 49 : value * 2 + '1' est donc beaucoup trop grand. Soustrais d’abord '0'.
Provoquer un dépassement de la valeur de position. Doubler power après le 31e chiffre donne 2^31, ce qui déborde ou provoque un plantage avec un entier de 32 bits.
Calculer chaque valeur de position à l’aide d’une fonction de puissance en virgule flottante. En C, C++ et Java, pow(2, k) renvoie un double, et le résultat doit être reconverti en entier.

Questions fréquentes4

Comment convertir un nombre binaire en nombre décimal ?

Attribuez à chaque chiffre une valeur de position : 1 pour celui le plus à droite, puis 2, 4, 8, et ainsi de suite vers la gauche. Additionnez les valeurs de position des chiffres qui valent 1. Pour 1101, cela donne 8 + 4 + 1 = 13.

Pourquoi le doublement de la valeur fonctionne-t-il ?

Écrire un chiffre de plus à la fin d’un nombre binaire déplace chaque chiffre précédent d’une position vers la gauche, et chaque position vaut deux fois celle qui se trouve à sa droite. Ainsi, l’ancienne valeur double, et le nouveau chiffre ajoute 0 ou 1. Répéter cette opération du premier chiffre au dernier permet de construire le nombre entier.

Quelle est la complexité temporelle de la conversion du binaire en décimal ?

Les deux boucles parcourent chacun des n caractères une fois, donc elles prennent un temps de O(n). Elles ne conservent qu’un ou deux nombres, ce qui représente un espace supplémentaire de O(1). Pour une chaîne de 31 caractères, cela fait 31 étapes.

Peux-tu convertir le binaire en décimal à l’aide de décalages de bits ?

Oui. value << 1 double la valeur et | digit définit le bit de poids faible, donc value = (value << 1) | digit fait la même chose que value * 2 + digit. La forme avec décalage montre clairement que tu déplaces des bits, tandis que la forme arithmétique fonctionne aussi pour les bases autres que 2.

Python

def toDecimal(s):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "1101"

Attendu