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.

and
Crédit : Bitwise Operators in Python link
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 link 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.

or
Crédit : Bitwise Operators in Python link
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.

not
Crédit : Bitwise Operators in Python link
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.

xor
Crédit : Bitwise Operators in Python link
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.
lshift
Crédit : Bitwise Operators in Python link
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 :

  1. >> 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).

  2. >>> 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.
rshift arithmetic
Crédit : Bitwise Operators in Python link
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

🞄  🞄  🞄