Outils pour utilisateurs

Outils du site


binaire

Calculs binaires

Objectif

Python sait faire du calcul binaire et de la manipulation de bits de nombres entiers. Mais comme le manuel n'est pas très explicite sur le sujet, je vais donner quelques exemples de ce qu'on peut faire avec.

Affichage de la représentation binaire d'un nombre entier

Avant de vouloir faire des manipulations en binaire, il faut savoir comment afficher la représentation binaire (des '0' et des '1') des nombres concernés.

Voilà un exemple de fonction qui transforme un nombre entier, en une chaine de caractères qui est sa représentation binaire:

def dec2bin(d,nb=8):
    """Représentation d'un nombre entier en chaine binaire (nb: nombre de bits du mot)"""
    if d == 0:
        return "0".zfill(nb)
    if d<0:
        d += 1<<nb
    b=""
    while d != 0:
        d, r = divmod(d, 2)
        b = "01"[r] + b
    return b.zfill(nb)

Exemples:

d = 92
 
print dec2bin(d)
01011100
 
d = 142
print dec2bin(d)
10001110
 
print dec2bin(d, 16)
0000000010001110

On voit dans ce code 2 lignes curieuses qui modifient l'argument d s'il est négatif. C'est pour corriger un problème: sans ces 2 lignes, la fonction ne supporterait pas les nombres négatifs. Or, on va forcément en avoir, parce que les nombres entiers de Python peuvent être négatifs. Par exemple, l'inversion des bits va forcément transformer un nombre positif en nombre négatif. On s'en tire ici avec une astuce: connaissant la longueur du mot utilisé, par défaut un octet=8 bits, un nombre négatif d aura la même représentation binaire que d + 256 qui, lui, sera positif. Donc, dans le cas général d'un mot de longueur nb, le nombre négatif d aura la même représentation binaire que d + (1<<nb).

En cas de nombre négatif, la fonction Python bin(d), présente depuis la version 2.6, ne donne pas de résultat satisfaisant pour nos besoins, puisque nous voulons avoir un représentation binaire complète (y compris le bit de signe s'il y en a un) et pas faire des calculs avec cette représentation binaire directement. Par exemple, pour la représentation de d=-1 qui est “11111111”:

d = -1
 
print dec2bin2(d)
11111111
 
print bin(d)
-0b1

Enfin, grâce à la fonction int(), on peut passer d'une représentation binaire sous forme de chaine à une représentation courante d'entier en base 10:

print int('01011100',2)
92
print dec2bin(92)
01011100

Opérateurs de base disponibles

Python nous donne 6 opérateurs de base pour agir directement sur les bits:

  • '&': et
  • '|': ou
  • '^': ou exclusif
  • '~': inversion des bits du nombre situé à droite
  • '»': décalage d'un bit à droite (correspond à une division par 2)
  • '«': décalage d'un bit à gauche (correspond à une multiplication par 2)

On peut ajouter aussi (sauf pour '~' qui est un signe unaire) tous les regroupements de ces opérateurs avec le signe d'affectation: '&=', '|=', '^=', '»=', '«=', ce qui permet de faire des calculs plus rapides. Par exemple, 'a &= b' correspond à: 'a = a & b'

Mais il y a aussi tous les opérateurs qui agissent sur les nombres entiers: '+', '+=', '-', '-=', '*', '*=', '//', '//=', '%', '%=', ainsi que divmod() qui fait d'un seul coup une division entière et un calcul de reste.

Reprenons chacun de ces opérateurs:

Opérateur '&' (et) et '&='

Si on cherche le résultat c = a & b, voilà comment on représente la manière dont les bits de a et de b vont se combiner:

& 0 1
0 0 0
1 0 1

Ce qui veut dire que pour qu'il y ait un '1' dans c, il faut qu'il y ait un '1' dans a, et un '1' dans b. Dans tous les autres cas, il y aura '0'.

Exemple:

a = 92    # 01011100
b = 21    # 00010101
c = a & b # 00010100

Avec cet opérateur, on peut donc filtrer et tester.

Exemple de filtrage: on va mettre à zéro les 4 bits de plus fort poids (ceux de gauche) de a, et laisser passer les autres:

a = 92    # 01011100
d = int('00001111',2) & a
print dec2bin2(d)
00001100

Exemple de test de bit: on va voir si le 4ème bit de a en partant de la droite est à '1' ou à '0'. Au lieu d'utiliser int('00001000',2), on peut utiliser: 1«(4-1):

a = 92    # 01011100
 
print bool(int('00001000',2) & a)
True
 
print bool((1<<(4-1)) & a)
True

Et test pour le 2ème bit à partir de la droite:

print bool(int('00000010',2) & a)
False

Opérateur '|' (ou) et '|='

Si on cherche le résultat c = a | b, voilà comment on représente la manière dont les bits de a et de b vont se combiner:

| 0 1
0 0 1
1 1 1

Ce qui veut dire que pour qu'il y ait un '1' dans c, il faut qu'il y en ait un dans a, ou dans b, ou dans a et b. Dans les autres cas (bit de a =0 et bit de b =0), il y aura '0'.

Opérateur '^' (ou exclusif) et '^='

Si on cherche le résultat c = a ^ b, voilà comment on représente la manière dont les bits de a et de b vont se combiner:

^ 0 1
0 0 1
1 1 0

Ce qui veut dire que pour qu'il y ait un '1' dans c, il faut qu'il y ait un '1' dans a, ou un '1' dans b (mais pas un '1' dans les 2!). Dans les autres cas, il y aura '0'.

Opérateur '~' (inversion)

Opérateur '>>' (décalage d'un bit à droite) et '>>='

Opérateur '<<' (décalage d'un bit à gauche) et '<<='

Effets des autres opérateurs de calcul

Quelques fonctions complémentaires de calcul binaire

Rotation à droite d'un mot de n bits, avec injection à gauche des bits perdus à droite

Rotation à droite de 1 bit

rotd = lambda b, n=8: ((b>>1)|(b<<(n-1)))&((1<<n)-1)

Rotation à droite de k bits (valable pour k de 0 à n, bornes incluses):

rotd = lambda b, k=1, n=8: ((b>>k)|(b<<(n-k)))&((1<<n)-1)

Simplification pour 8 bits (valable pour k de 0 à 8, bornes incluses)

rotd = lambda b, k=1: ((b>>k)|(b<<(8-k)))&0xFF

Rotation à gauche d'un mot de n bits, avec injection à droite des bits perdus à gauche

Rotation à gauche de 1 bit

rotg = lambda b, n=8: ((b<<1)|(b>>(n-1)))&((1<<n)-1)

Rotation à gauche de k bits (valable pour k de 0 à n, bornes incluses):

rotg = lambda b, k=1, n=8: ((b<<k)|(b>>(n-k)))&((1<<n)-1)

Simplification pour 8 bits (valable pour k de 0 à 8, bornes incluses)

rotg = lambda b, k=1: ((b<<k)|(b>>(8-k)))&0xFF


Amusez-vous bien!

binaire.txt · Dernière modification: 2012/03/06 14:25 de tyrtamos

Outils de la page