Opérations bit à bit

Ce billet date de plusieurs années, ses informations peuvent être devenues obsolètes.

Les langages de haut niveau (dont Python et JavaScript) permettent d'aller travailler au niveau du bit grâce aux opérations bit à bit (bitwise).

En règle générale, ces opérations sont plutôt utilisées dans la programmation bas niveau ou embarquée. Pour des langages proches de la machine, ce sont des opérations très rapides.

Pour des langages de haut niveau, c'est plus compliqué. Par exemple en JavaScript les opérateurs bit à bit fonctionnent sur des entiers alors que les nombres sont représentés par des flottants en double précision qui doivent donc être convertis.

Bref, vous en verrez peu dans une carrière de développeur web mais ça fait partie de la science du computer. Alors autant en connaître le b.a.-ba.

Calcul binaire à la main

Utile pour la culture ou si un jour vous voulez faire du langage d'assemblage.

Les opérations arithmétiques "à la main" (addition, soustraction, multiplication et division) fonctionnent presque comme en décimal…

…sauf que le compteur ne tourne pas après 9 mais après 1. Ça n'est pas très fluide au début car notre cerveau est complètement conditionné à la base 10.

Pour le cas 0 - 1 de la soustraction binaire, la retenue est causée par l'ajout d'une unité binaire à 0 qui devient 10, c'est à dire un et zéro en binaire ou 2 en décimal.

Les anglo-saxons utilisent la méthode par emprunt plutôt que la méthode par compensation pour soustraire. C'est important à savoir si vous allez lire des articles en anglais sur le sujet.

Au travail !

Opérateurs binaires

Deux catégories d'opérations permettent de travailler au niveau des bits : les instructions logiques et de décalage.

Ces instructions travaillent sur des entiers relatifs et au format du complément à deux.

Instructions logiques

Les instructions logiques sont basées sur l'algèbre de Boole et ses tables de vérité :

Variables OR XOR AND NOT
x y x | y x ^ y x & y ~x
0 0 0 0 0 1
0 1 1 1 0 1
1 0 1 1 0 0
1 1 1 0 1 0

OR (|) est le OU inclusif qui signifie que l'une ou l'autre des affirmations, ou toutes, sont vraies.

XOR (^) est le OU exclusif, c'est à dire fromage ou dessert mais pas les deux à la fois.

AND (&), OR (|) et XOR (^) prennent deux opérandes et font une comparaison bit par bit à chacun des emplacements (comme une opération manuelle).

NOT (~) inverse les bits et c'est le seul opérateur qui prend un seul opérande, on parle d'opérateur unaire.

Instructions de décalage

Les instructions de décalage de bits déplacent littéralement les bits vers la gauche x << n ou vers la droite x >> n d'un nombre n de rangs.

Pendant ces déplacements, certains bits sont inconnus, ce qui laisse des places vides qu'il faut combler : ils sont remplis avec des zéros par décalage arithmétique en préservant le signe.

Le décalage à gauche est équivalent à une multiplication par une puissance de 2, exactement comme si en base 10 on décalait tout à gauche en ajoutant deux 0 à la fin : ça reviendrait à multiplier par 102.

Le décalage à droite est équivalent à une division par une puissance de 2.

JavaScript dispose en plus du décalage logique à droite : x >>> n (trois fois le signe >) qui ne préserve pas le signe.

Opérations usuelles sur les bits

Les opérations suivantes sont une bonne introduction pour voir ce que l'on peut faire avec les instructions bit à bit.

Elles ont pour point commun d'utiliser des masques binaires.

Masques binaires

Les plus simples sont composés :

  • d'une série de bits à 0 et d'un seul bit à 1 à une position spécifique : 10000
  • d'une série de bits à 1 et d'un seul bit à 0 à une position spécifique : 01111 (masque inversé)

Pour créer un masque on se sert de l'opérateur de décalage vers la gauche qui va pousser notre 1 en remplissant avec des 0.

Par exemple en JavaScript pour avoir 1 en 2ème position :

let mask = 1 << 2
mask.toString(2)   // 100

Pour créer un masque inversé on fait la même chose en appliquant un NOT (~) pour inverser le résultat :

let mask = ~(1 << 2)
mask.toString(2)   // 101

Remarquez que la sortie de toString(2) ne correspond pas à la valeur en bits attendue (011) !

On va reprendre par étapes pour voir ce qui se passe :

> let n = 1 << 2
> n
4

Le résultat de l'opération ci-dessus est le nombre 4 représenté sur 32 bits par :

0000 0000 0000 0000 0000 0000 0000 0100

Ensuite on inverse les bits :

> n = ~n
-5

Les 32 bits ont été inversés :

1111 1111 1111 1111 1111 1111 1111 1011

L'interprétation au format du complément à deux de ces bits inversés donne -5.

Ensuite, la façon dont fonctionne toString(2) en base 2 est de prendre la valeur décimale absolue (ici 5), puis de la représenter en binaire en y ajoutant le signe - :

> n.toString(2)
'-101'

On a donc -101 en sortie de toString(2) !

Il y a une astuce pour voir les vrais bits en utilisant le décalage logique >>> (le slice est utilisé pour le confort de lecture) :

> (n >>> 0).toString(2)
'1111 1111 1111 1111 1111 1111 1111 1011'
> (n >>> 0).toString(2).slice(-n.toString(2).length + 1)
'011'

Forcer le nième bit à 1

On utilise un masque qui indique la position du bit à mettre à 1.

On fait un OR (|) entre le nombre et le masque pour que le bit indiqué par le masque devienne 1 quelle que soit sa valeur initiale (c.f. table de vérité) :

let setBit = (num, i) => {
    let mask = 1 << i
    return num | mask
}

let n = 8
n.toString(2)  // 1000

n = setBit(n, 0)
n.toString(2)  // 1001

Forcer le nième bit à 0

On utilise un masque inversé qui indique la position du bit à mettre à 0.

On fait un AND (&) entre le nombre et le masque pour que le bit indiqué par le masque devienne 0 quelle que soit sa valeur initiale (c.f. table de vérité) :

let clearBit = (num, i) => {
    let mask = ~(1 << i)
    return num & mask
}

let n = 15
n.toString(2)  // 1111

n = clearBit(n, 2)
n.toString(2)  // 1011

Trouver la valeur du nième bit

On utilise un masque qui indique la position du bit dont on veut trouver la valeur.

On fait un AND (&) entre le nombre et le masque.

D'après la table de vérité, si le résultat de l'opération n'est pas 0, alors c'est que le bit à la position donnée vaut 1 :

let getBit = (num, i) => {
    let mask = 1 << i
    return (num & mask) !== 0
}

let n = 10
n.toString(2)  // 1010

console.log(getBit(n, 0))  // false
console.log(getBit(n, 3))  // true

Mettre à jour le nième bit

On commence par forcer le nième bit à 0 (c.f. technique précédente).

Ensuite on se sert d'un autre masque dont le nième bit est 1 ou 0 en fonction de la valeur que l'on souhaite mettre à jour.

Il ne reste plus qu'à faire un OR (|) entre le nombre avec le nième bit forcé à 0 et le masque de la nouvelle valeur (c.f. table de vérité) :

let updateBit = (num, i, value) => {

    let clearMask = ~(1 << i)
    let clearedNum = num & clearMask

    value = value ? 1 : 0;
    let valueMask = value << i
    return clearedNum | valueMask

}

let n = 21
n.toString(2)  // 10101

n = updateBit(n, 3, 1)
n.toString(2)  // 11101

Les pros utilisent une syntaxe moins verbeuse mais ça pique les yeux quand on n'est pas habitué :

let n = 21
n &= ~(1 << 3)
n |= (1 << 3)
n.toString(2)  // 11101

Sources

Voilà.

Je commence un peu à en avoir ras-le-booleen maintenant…

Et surtout n'oubliez jamais : XOR, sur la terre il est comme toi et moi ! Rēzā Burēdo > Lightsaber !

Avant Binaire, hex, et représentation des nombres Après Rétrospective pour les 30 ans du Web

Tag Kemar Joint