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.
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
Python nous donne 6 opérateurs de base pour agir directement sur les bits:
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:
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
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'.
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'.
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 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!