Conversions entre un nombre entier et sa représentation binaire, y compris binaire signée (complément à 2)

Cette fonction permet de convertir un nombre entier positif ou nul, dans sa représentation binaire. Par exemple:

dec2bin(75) => "1001011"

Il est aussi possible de fixer la longueur du mot en nombre de bits, et la chaîne binaire est alors complétée si nécessaire avec des “0” à gauche. Par exemple pour un mot de 12 bits:

dec2bin(75,12) => "000001001011"

Le principe de calcul est le suivant. On part du nombre d. Si d est pair, son bit de droite est “0”, sinon, il est “1”. On remplace alors d par d divisé par 2 et on recommence en ajoutant le résultat (“0” ou “1”) à gauche de la chaîne cherchée b. Jusqu'à ce que d soit nul. Et on renvoie la chaîne binaire b.

Comme cet algorithme renvoie une chaîne vide lorsque d=0, on traite ce cas dès le départ en renvoyant b=“0”.

Au lieu de renvoyer simplement b, on renvoie b.zfill(nb) qui complète éventuellement par des “0” à gauche de b pour que la chaîne binaire soit de la longueur demandée par nb. Bien sûr, quand nb=0 ou non donné à l'appel de la fonction, rien n'est ajouté.

Pour diminuer le temps de calcul, on a utilisé des opérations sur les bits au lieu des opérations de calcul habituels:

• d>>1 correspond à d//2 (= division entière par 2)
• d&1 correspondant à d%2 ou d modulo 2 (= reste de la division entière par 2)

Egalement pour gagner du temps, on utilise une astuce pour convertir le chiffre 0 ou 1 en caractère “0 ou “1”:

• "01"[0] donne "0"
• "01"[1] donne "1"

Voilà le code proposé:

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def dec2bin(d,nb=0):
    """dec2bin(d,nb=0): conversion nombre entier positif ou nul -> chaîne binaire (si nb>0, complète à gauche par des zéros)"""
    if d==0:
        b="0"
    else:
        b=""
        while d!=0:
            b="01"[d&1]+b
            d=d>>1
    return b.zfill(nb)
 
# Exemple d'utilisation:
print dec2bin(75)  # affiche: "1001011"
print dec2bin(75,12)  # affiche: "000001001011" 

Cette fonction permet de convertir un nombre entier quelconque positif ou négatif, dans sa représentation binaire signée. Par exemple:

dec2bins(-91) =>        "10100101"
dec2bins(-91,12) => "111110100101"

dec2bins(-41) =>         "1010111"
dec2bins(-41,8) =>      "11010111"

Principe de la représentation binaire signée avec le “complément à 2”. Exemple avec le nombre négatif -91:

• représentation binaire de +91 ⇒ 1011011
• on inverse les bits (0 devient 1 et 1 devient 0) ⇒ 0100100
• et on ajoute +1 (avec retenues éventuelles!) ⇒ 0100101
• il ne reste plus qu'à ajouter un bit de signe à gauche de la chaine binaire: “1” pour un nombre négatif ⇒ 10100101.

Avec cette opération, un mot de 8 bits, qui aurait pu représenter des valeurs positives entre 0 et 255, pourra contenir des valeurs signées entre -128 et +127.

La taille minimale d'un binaire signée est de 2 bits, soit un bit de donnée et un bit de signe. Cela permet de coder 4 valeurs:

• -2 => "10"
• -1 => "11"
• 0 => "00"
• +1 => "01"

Vous voyez d'ailleurs avec cet exemple, que la représentation binaire signée de 0 n'est pas “0”, mais “00” parce qu'il faut le bit de signe!

Vous vous rendez bien compte que la taille du mot compte dans la représentation binaire signée:

• la représentation binaire signée doit avoir à gauche un bit de signe, égal à “0” pour un nombre positif, et “1” pour un nombre négatif.

• la représentation de -91 nécessitera au minimum un mot de 8 bits, puisqu'il faut 7 bits pour le représenter + 1 bit de signe à gauche qui sera “1” puisque ce nombre est négatif.

• pour représenter un même nombre signé dans un mot plus grand, il suffit:
  • s'il est positif ou nul, d'ajouter des “0” à gauche de la chaine binaire, le dernier “0 à gauche étant le bit de signe. Exemple: +91 dans un mot de 12 bits ⇒ 000001011011
  • s'il est négatif, d'ajouter des “1” à gauche de la chaine binaire, le dernier “1” à gauche étant le bit de signe. Exemple: -91 dans un mot de 12 bits ⇒ 111110100101

Dans une version précédente de la fonction dec2bins(), je rendais obligatoire de donner la taille du mot. J'ai adopté ici un mode de calcul plus général:

• si la taille du mot n'est pas donnée, on calcule la taille du mot minimale capable de contenir le nombre d en binaire signé.

• avec la taille du mot “nb” (nb pour “nombre de bits”) donnée à l'appel de la fonction ou calculée comme ci-dessus, on calcule la représentation binaire de d de la façon suivante:
  • si d est positif ou nul, on renvoie la même chose que dec2bin(d,nb) le “0” le plus à gauche étant pris comme bit de signe.
  • si d est négatif, on renvoie dec2bin((1<<nb)-abs(d)). En effet, la représentation binaire signée de -91 dans un mot de 8 bits, est identique à la représentation binaire non-signée de (1<<8)-91 soit +165.

Tout cela suppose, bien entendu, que la taille du mot donnée soit suffisante pour représenter le nombre donné en binaire signé! Pour rester simple, le code ci-dessous n'a fait aucune vérification des données.

Utilise la fonction dec2bin() décrite plus haut.

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def dec2bins(d,nb=0):
    """dec2bins(d,nb=0): conversion nombre entier signé d -> chaîne binaire pour un mot de nb bits (=0 par defaut) """
    # calcul de la taille mini du mot permettant de représenter la valeur signée d (signe compris)
    n=1
    if d>=0:
        x=d
    else:
        x=-d-1
    while (1<<n)<=x:
        n+=1
    n+=1
    # valeur de nb à prendre pour la suite des calculs (si nb<n, le nb donné est trop faible pour le d donné)
    if (nb==0) or (nb<n):
        nb=n
    # calculs
    if d>=0:
        # on renvoie la chaîne normale, complétée par des "0" à gauche et par le bit de signe = "0"
        b='0' + dec2bin(d,nb-1)
    else:
        # on renvoie la chaîne signée, complétée par des "1" à gauche et par le bit de signe "1"
        b='1' + dec2bin((1<<(nb-1))+d,(nb-1))
    return b
 
# Exemple d'utilisation:
print dec2bins(-2) # affiche: '10'
print dec2bins(-1) # affiche: '11'
print dec2bins(0) # affiche: '00'
print dec2bins(1) # affiche: '01'
print
print dec2bins(-2,8) # affiche: '11111110'
print dec2bins(135) # affiche: '010000111'
print dec2bins(135,16) # affiche: '0000000010000111'
print dec2bins(-75) # affiche: '10110101'
print dec2bins(-75,8) # affiche: '10110101'
print dec2bins(-91) # affiche: '10100101'
print dec2bins(-91,12) # affiche: '111110100101'
print dec2bins(-41) # affiche: '1010111'
print dec2bins(-41,8) # affiche: '11010111'
print dec2bins(2,8) # affiche: '00000010'
print dec2bin(s127,8) # affiche: '01111111'
print dec2bins(127,12) # affiche: '000001111111'
print dec2bins(0,8) # affiche: '00000000'

Ça, c'était facile: ça existe déjà dans Python! Exemple:

int("1001011",2) => 75

Pour des raisons d'homogénéité, et afin de pouvoir faire des contrôles sur la donnée, je propose une fonction qui fait la même chose:

bin2dec("1001011") => 75

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def bin2dec(b):
    """bin2dec(b): Conversion chaîne binaire de longueur quelconque -> nombre entier positif"""
    return int(b,2)
 
# Exemple d'utilisation:
print bin2dec("1001011")  # affiche 75

Cette fonction permet de convertir une chaîne binaire signée en nombre positif ou négatif. Par exemple:

bin2decs("111110100101") => -91

Le principe de calcul est simple:

• si le caractère de gauche est “0”, alors, le nombre est positif, et sa valeur sera obtenue avec int(chainebinaire,2).

• si le caractère de gauche est “1”, alors le nombre est négatif, et sa valeur sera obtenue avec int(b,2)-(1<<len(b)). Cette expression est le contraire de ce nous avons utilisé plus haut. Nous avions dit que, par exemple, la représentation binaire signée de -91 était la même que la représentation binaire non-signée de 256-91=165 (la formule était (1<<nb)-abs(d) ).

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def bin2decs(C):
    """bin2decs(C): Conversion chaîne binaire signée de longueur quelconque -> nombre entier signé"""
    if C[0]=="0":
        # le 1er chiffre est un '0' => le résultat sera positif
        return int(C,2)
    else:
        # le 1er chiffre est un '1' => le résultat sera négatif
        return int(C,2)-(1<<len(C))
 
# Exemple d'utilisation:
print bin2decs("111110100101")  # affiche -91