Decimal to Binary

Q: Peux-tu convertir en binaire avec des opérations sur les bits plutôt qu’avec la division ?

Oui. n & 1 donne le bit de poids faible et n >> 1 le supprime, ce qui revient à n % 2 et n / 2 pour les nombres non négatifs. La boucle et l’inversion restent les mêmes. La division est plus facile à expliquer, tandis que la version avec décalage est courante dans le code de bas niveau.

DébutantMaths et simulation Manipulation de bits

+10

On vous donne un entier non négatif n. Renvoyez sa représentation binaire sous forme de chaîne composée de 0 et de 1, sans zéros en tête. Le seul nombre dont la réponse commence par 0 est zéro lui-même, qui s’écrit "0".

Fonction

toBinary(n: integer) → string

ninteger: le nombre à convertir
Renvoiestring: les chiffres binaires de n sous forme de chaîne

Contraintes

0 ≤ n ≤ 2³¹-1
Construisez vous-même la chaîne au lieu d’appeler une conversion de base intégrée.

Exemples

Entrée: n = 13
Sortie: "1101"
Explication: 13 = 8 + 4 + 1. Les positions correspondant à 8, 4, 2 et 1 contiennent 1, 1, 0 et 1, ce qui donne 1101.

Entrée: n = 0
Sortie: "0"
Explication: Zéro n’a aucun bit défini, mais la réponse doit tout de même contenir un chiffre : c’est donc "0" et non une chaîne vide.

Entrée: n = 64
Sortie: "1000000"
Explication: 64 est 2^6, un seul 1 à la position des 64, suivi de six 0 pour les positions de 32 à 1.

+16 tests cachés à la soumission

Pour aller plus loin

Peux-tu convertir n dans n’importe quelle base de 2 à 16 avec la même boucle, en utilisant les lettres a à f pour les chiffres supérieurs à 9 ?

Indices

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

0 sur 3 ouverts

Solution

Un nombre binaire est une somme de puissances de deux, et chaque chiffre indique si une puissance fait partie de la somme. Tu peux déterminer les chiffres en partant du haut en soustrayant des puissances de deux, ou les lire en partant du bas comme les restes de divisions répétées par 2. La boucle de division est la méthode standard : elle n’a jamais besoin de trouver d’abord la plus grande puissance, et elle fonctionne de la même manière pour chaque base.

Soustraire des puissances de deux à partir du haut

Intuition

Voici comment effectuer la conversion à la main. Trouve la plus grande puissance de deux qui tient dans n ; c’est le premier chiffre, un 1. Puis descends d’une puissance à la fois. Si la puissance tient encore dans ce qu’il reste, écris 1 et soustrais-la ; sinon, écris 0.

Pour 13, la plus grande puissance est 8. Écris 1 et garde 5. Ensuite, 4 tient (1, garde 1), 2 ne tient pas (0), et 1 tient (1). Les chiffres donnent 1101. Le premier chiffre est toujours un 1, donc aucun zéro initial ne peut apparaître.

Trouver la plus grande puissance demande de la prudence. Doubler power jusqu’à ce qu’il dépasse n provoque un dépassement de capacité d’un entier 32 bits dès que n ≥ 2^30, car la puissance suivante est 2^31. Doubler seulement tant que power ≤ n / 2 permet de s’arrêter à la bonne puissance sans jamais dépasser n. Un nombre de 31 bits prend 31 étapes, soit O(log n).

Algorithme

Si n vaut 0, renvoie "0".
Initialise power à 1 et double-le tant que power ≤ n / 2.
Tant que power > 0 : si n ≥ power, ajoute 1 et soustrais power de n ; sinon, ajoute 0.
Divise power par deux et recommence.
Renvoie les chiffres que tu as ajoutés.

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)

Divisions répétées par 2

Intuition

Le dernier chiffre binaire de n indique si n est impair, ce qui correspond à n % 2. Diviser par 2 et supprimer le reste décale chaque chiffre d’une position vers la droite, de sorte que le chiffre suivant devient le dernier. Répète jusqu’à ce qu’il ne reste plus rien et récupère chaque chiffre, en commençant par le moins significatif.

Pour 13 : 13 donne un reste de 1, 6 donne 0, 3 donne 1 et 1 donne 1, puis le nombre vaut 0. Les restes dans l’ordre sont 1, 0, 1, 1 ; inversés, ils donnent 1101. La boucle s’arrête lorsque le nombre atteint 0 : le chiffre le plus significatif qu’elle écrit est donc toujours un 1, et aucun zéro initial n’apparaît. Zéro lui-même n’entre jamais dans la boucle, c’est pourquoi il faut le traiter séparément.

Chaque étape divise le nombre par deux ; une valeur sur 31 bits nécessite donc 31 étapes, soit un temps en O(log n), et la chaîne de chiffres occupe un espace en O(log n).

Algorithme

Si n vaut 0, renvoie "0".
Tant que n > 0, ajoute n % 2 comme chiffre et définis n à n / 2, arrondi à l’entier inférieur.
Inverse les chiffres, car ils sont sortis du plus petit au plus grand.
Renvoie-les sous forme de chaîne.

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)

Pièges et cas limites

La boucle est courte, et la plupart des mauvaises réponses viennent de ses deux extrémités.

Renvoyer une chaîne vide pour 0. La boucle de division ne s’exécute jamais pour zéro, alors vérifie d’abord ce cas.
Oublier d’inverser. Les restes arrivent du chiffre le moins significatif au plus significatif, donc 6 donne 011 au lieu de 110.
Utiliser / dans un langage où cet opérateur renvoie une fraction, comme JavaScript, Lua ou PHP. 13 / 2 doit donner 6, alors arrondis vers le bas ou utilise la division entière.
Construire la plus grande puissance en doublant jusqu’à dépasser n. Pour n = 2^31-1, la puissance suivante, 2^31, ne tient pas dans un entier de 32 bits.
Allouer trop peu de mémoire en C. Un nombre sur 31 bits nécessite 31 caractères plus le caractère de fin '\0'.

Questions fréquentes4

Comment convertir un nombre décimal en binaire ?

Divisez le nombre par 2 encore et encore, en notant chaque reste, jusqu’à ce que le nombre atteigne 0. Lisez les restes du dernier au premier. Pour 13, les restes sont 1, 0, 1, 1, donc 13 en binaire s’écrit 1101.

Pourquoi les restes sont-ils lus dans l’ordre inverse ?

La première division par 2 vous indique si le nombre est impair, ce qui correspond au dernier chiffre binaire. Chaque division suivante révèle le chiffre suivant vers la gauche. Les restes apparaissent donc en commençant par le chiffre de poids faible, et vous les inversez pour écrire le nombre dans le sens habituel.

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

Chaque étape divise le nombre par deux, donc la boucle s’exécute une fois par chiffre binaire, soit environ log2(n) fois. Cela prend un temps de O(log n), et la chaîne de réponse occupe un espace de O(log n). Pour un entier de 32 bits, cela représente au plus 31 étapes.

Peux-tu convertir en binaire avec des opérations sur les bits plutôt qu’avec la division ?

Oui. n & 1 donne le bit de poids faible et n >> 1 le supprime, ce qui revient à n % 2 et n / 2 pour les nombres non négatifs. La boucle et l’inversion restent les mêmes. La division est plus facile à expliquer, tandis que la version avec décalage est courante dans le code de bas niveau.

Python

def toBinary(n):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

n = 13

Attendu

"1101"