Les opérations bit à bit Préambule Python sait faire du calcul binaire et de la manipulation de bits sur les nombres entiers. Ceci est utile lorsqu’on désire intervenir sur une seule portion d’une valeur binaire. Pour cela, on dispose d’opérateurs appelés bit à bit ou bitwise en anglais. Opérateur Signification Exemple & ET bit à bit a & b | OU bit à bit a | b ^ OU EXCLUSIF bit à bit a ^ b ~ NON bit à bit ~a << Décalage à gauche a << n >> Décalage à droite a >> n Les opérations bit à bit sont utilisées dans de nombreux domaines de l’informatique : programmation “bas niveau” (i.e. proche du matériel) → accès aux registres d’un microprosseur, accès aux broches d’entrée/sortie du système réseau → masques de sous-réseau imagerie → retouche photo, traitement d’images jeux vidéo → sprites, bit blit Toutes ces applications reposent sur des manipulations de base réalisées à partir des opérateurs vus plus haut : le forçage à 1 ou à 0 d’un ou plusieurs bits le test de la valeur d’un ou plusieurs bits l’inversion de la valeurs d’un ou plusieurs bits la détermination du nombre de bits à 0 ou à 1 d’une valeur binaire l’inversion de l’ordre des bits d’une valeur binaire … Opérations de base L’opérateur & L’opérateur & effectue un ET binaire entre les bits occupant la même position dans ses opérandes. Pour chaque paire de bits, il ne renvoie 1 que si les 2 bits sont à 1. Crédit : Bitwise Operators in Python Même calcul dans l’interpréteur Python : >>> a = 0b10011100 >>> b = 0b00110100 >>> r = a & b >>> f"{r:08b}" (1) '00010100' 1 Utilisation d’une f-string Python pour afficher le résultat sur 8 bits. Voir Écriture formatée pour plus de détails sur les f-strings. L’opérateur | L’opérateur | effectue un OU binaire entre les bits occupant la même position dans ses opérandes. Il renvoie 1 si au moins l’un des 2 bits est à 1. Crédit : Bitwise Operators in Python Même calcul dans l’interpréteur Python >>> a = 0b10011100 >>> b = 0b00110100 >>> r = a | b >>> f"{r:08b}" '10111100' L’opérateur ~ L’opérateur ~ effectue une négation binaire des bits de son opérande. Il inverse la valeur de chacun des bits. Crédit : Bitwise Operators in Python Même calcul dans l’interpréteur Python : >>> a = 0b00110100 >>> r = ~a >>> f"{r % 256:08b}" (1) '11001011' 1 On utilise ici une astuce (→ r % 256) pour que Python ne considère pas le résultat comme un nombre négatif du fait de la présence d’un 1 dans le bit de poids fort. Représentation en mémoire des entiers en Python Python, contrairement à la majorité des autres langages, ne code pas les entiers en mémoire sur un nombre fixe d’octets (ex. : 4 ou 8 selon le type d’entier en langage C) : il utilise autant d’octets que nécessaire pour représenter le nombre. Pour savoir combien d’octets sont utilisés pour représenter un entier en mémoire, on peut utiliser la fonction getsizeof() du module sys : Exemple : >>> import sys >>> sys.getsizeof(0) 28 (1) >>> sys.getsizeof(1024) 28 >>> sys.getsizeof(123456789123456789) 32 (2) >>> sys.getsizeof(-1024) 28 >>> sys.getsizeof(-123456789123456789) 32 1 28 octets sont nécessaires pour coder 0 en mémoire. 2 32 octets sont nécessaires pour coder 123456789123456789 Dans cette suite d’octets, le bit le plus à gauche est utilisé pour coder le signe du nombre. Le reste est utilisé pour coder la valeur absolue du nombre. Cette notation porte le nom de signe-magnitude (⇒ Python n’utilise donc pas le complément à 2 pour représenter les nombres entiers relatifs en mémoire). Le complément à 2 sera malgré tout utilisé lors des opérations bit à bit (représentation signe-magnitude de l’opérande ⇒ représentation en complément à 2 de l’opérande ⇒ opération bit à bit en complément à 2 ⇒ représentation signe-magnitude du résultat). Tout ceci fait qu’il faut parfois avoir recours à quelques artifices (ex. : r % 256 dans l’exemple vu plus haut) lorsqu’on désire afficher le résultat d’une opération bit à bit. L’opérateur ^ L’opérateur ^ effectue un OU EXCLUSIF binaire entre les bits occupant la même position dans ses opérandes. Il renvoie 1 si un et un seul des 2 bits est à 1. Crédit : Bitwise Operators in Python Même calcul dans l’interpréteur Python : >>> a = 0b10011100 >>> b = 0b00110100 >>> r = a ^ b >>> f"{r:08b}" '10101000' L’opérateur << L’opérateur << de décalage vers la gauche déplace les bits de son premier opérande vers la gauche du nombre de places spécifié dans son second opérande. Il se charge également d’insérer suffisamment de bits à 0 pour combler le vide qui apparaît sur le bord droit du résultat. Un décalage à gauche de N positions d’une valeur revient à la multiplier par 2N. Crédit : Bitwise Operators in Python Même calcul dans l’interpréteur Python : >>> a = 0b10011101 (1) >>> r = a << 1 (2) >>> f"{r:b}" '100111010' (3) >>> f"{r & 0xff:08b}" '00111010' (4) 1 a = 10011101|2 = 157|10 2 décalage à gauche d’une position 3 résultat sur 9 bits : r = 100111010|2 = 314|10 (= 2 * 157). 4 ⚠ Si on tronque le résultat sur 8 bits , comme dans l’illustration, le résultat n’est bien entendu plus le double de 157 ([X]00111010|2 ⇒ 58|10) L’opérateur >> L’opérateur >> de décalage vers la droite déplace les bits de son premier opérande vers la droite du nombre de places spécifié dans son second opérande. Un décalage à droite de N positions d’une valeur revient à la diviser par 2N. Cependant, à l’inverse du décalage à gauche, la valeur des bits insérés à gauche lors du décalage à droite dépendent du signe du 1er opérande. Ainsi, si le 1er opérande est positif, des 0s seront ajoutés à gauche. À l’inverse, si le 1er opérande est négatif, ce seront des 1s qui seront ajoutés à gauche. De cette façon, le signe est maintenu : on parle alors de décalage à droite arithmétique (ou décalage à droite signé). La langage Python ne définit que des décalages à droite arithmétiques contrairement à Javascript par exemple. Ce dernier dispose en effet de 2 opérateurs distincts pour les décalages : >> pour le décalage à droite arithmétique (→ Javascript insère des bits à gauche dont la valeur dépend du signe de l’opérande (des 1s si l’opérande est négatif et des 0s si l’opérande est positif, comme en Python). >>> pour le décalage à droite logique (→ Javascript insère systématiquement des 0s à gauche, quel que soit le signe de l’opérande). Il sera néanmoins possible de faire des décalages à droite logiques en Python, mais au prix de manipulations supplémentaires. Crédit : Bitwise Operators in Python Même calcul dans l’interpréteur Python : >>> a = -100 >>> f"{a:b}" '-1100100' (1) >>> f"{a & 0xff:b}" '10011100' (2) >>> r = a >> 1 (3) >>> f"{r & 0xff:b}" '11001110' (4) >>> f"{r:b}" '-110010' (5) 1 représentation signe-magnitude de -100 2 représentation en complément à 2 de -100 en utilisant l’artifice consistant à faire un ET bit à bit entre le nombre et la valeur 0xff (→ 11111111|2) 3 décalage arithmétique à droite d’une position 4 représentation en complément à 2 du résultat (→ un 1 a été ajouté à gauche pour maintenir le signe). 11001110|2 en complément à 2 donne bien -50|10 (un décalage à droite revient à diviser par 2). 5 représentation signe magnitude de -50|10 (→ “-110010” : signe ‘-’ puis 25 + 24 + 21 = 32 + 16 + 2 = 50 ⇒ r = -50) Exemple d’utilisation des opérateurs bit à bit Comme indiqué dans le préambule, les opérateurs bit à bit ont une utilité dans plusieurs domaines dont le réseau, pour la détermination des masque de réseau, IP réseau… Voici un exemple de script Python qui calcule un ensemble de valeurs à partir d’une adresse IP exprimée en notation CIDR (IP + longueur du masque). Code source ipcalc.py def cidr2Binary(address) : """Retourne un tuple (ip,mask) contenant l'ip ainsi que le masque sur 32 bits d'une adresse d'hôte exprimée en notation CIDR. arguments: address -- l'adresse IPv4 d'un hôte sous forme d'une chaîne en notation CIDR """ # Extraction de l'adresse IP en notation décimale pointée et de la longueur du masque # depuis l'adresse de l'hôte fournie en notation CIDR ipDotDecimal,maskLen = address.split('/') # Calcul du masque sur 32 bits à partir de sa longueur exprimée dans la notation CIDR fullMask = 0xffffffff # nombre de 32 bits rempli de 1. # On aurait aussi pu écrire : fullMask = (1 << 32) - 1 mask = (fullMask << (32 - int(maskLen))) & 0xffffffff # Calcul de l'adresse IP sur 32 bit à partir de la notation décimale pointée ipFields = ipDotDecimal.split('.') ip = 0 for f in ipFields : ip = (ip << 8) | int(f) return (ip,mask) def binary2DotDecimal(binaryIp) : """ Retourne une chaîne représentant une IP exprimée sur 32 bits en notation décimale pointée. arguments: binaryIP : adresse IP sur 32 bits """ # Découper l'ip donnée sur 32 bits en 4 nombres en représentation décimale ipFields= [] for i in range (3,-1,-1) : ipFields.append(str(((binaryIp >> (i * 8)) & 0xff))) # Retourner l'IP en notation décimale pointée (en joignant les 4 nombres # en représentation décimale avec un '.') return '.'.join(ipFields) if __name__=="__main__": # Adresse IP de l'hôte à analyser hostAddress = "192.168.7.254/22" print(f">>>> {hostAddress} <<<<") # Conversion de l'adresse de l'hôte en IP et Masque sur 32 bits # afin de pouvoir réaliser les différents calculs avec les opérateurs # bit à bit hostIpBinary,maskBinary = cidr2Binary(hostAddress) # Affichage de l'adresse IP et du masque en notation décimale pointée hostIpDotDecimal = binary2DotDecimal(hostIpBinary) maskDotDecimal = binary2DotDecimal(maskBinary) print(f"host IP\t\t: {hostIpDotDecimal}") print(f"Mask\t\t: {maskDotDecimal}") # Détermination de l'adresse réseau [-> adresse hôte ET masque] networkBinary = hostIpBinary & maskBinary netwrokDotDecimal = binary2DotDecimal(networkBinary) print(f"Network address\t: {netwrokDotDecimal}") # Détermination de l'adresse de broadcast [-> adresse réseau OU (NON Masque)] broadcastBinary = networkBinary | ~maskBinary broadcastDotDecimal = binary2DotDecimal(broadcastBinary) print(f"Broadcast IP\t: {broadcastDotDecimal}") # Détermination de l'adresse IP du 1er hôte [-> adresse réseau + 1] firstHostBinary = networkBinary + 1 firstHostDotDecimal = binary2DotDecimal(firstHostBinary) print(f"First Host IP\t: {firstHostDotDecimal}") # Détermination de l'adresse IP du dernier hôte [-> adresse broadcast - 1] lastHostBinary = broadcastBinary - 1 lastHostDotDecimal = binary2DotDecimal(lastHostBinary) print(f"Last Host IP\t: {lastHostDotDecimal}") # Détermination du nombre d'hôtes max. dans le réseau maskLen = int(hostAddress.split('/')[1]) nbHosts = 2 ** (32 - maskLen) - 2 print(f"Nb hosts max.\t: {nbHosts}") Résultat d’exécution : >>>> 192.168.7.254/22 <<<< host IP : 192.168.7.254 Mask : 255.255.252.0 Network address : 192.168.4.0 Broadcast IP : 192.168.7.255 First Host IP : 192.168.4.1 Last Host IP : 192.168.7.254 Nb hosts max. : 1022 🞄 🞄 🞄 Codage des nombres à virgule Algèbre