Entiers et manipulation de bits

1 Introduction

Java comporte cinq types primitifs dits types entiers (integral types) : byte, short, int, long et char. Malgré leur nom, aucun ne correspond vraiment à la notion mathématique d'entier — l'ensemble \(\mathbb Z\) — car tous ne peuvent représenter qu'un nombre fini de valeurs. Ainsi, aucun d'entre eux ne peut représenter l'entier 1020

En raison de ce nombre limité de valeurs représentables, les opérations arithmétiques sur ces entiers (addition, soustraction, etc.) ont un comportement parfois différent de leurs équivalents mathématiques. Il est bon de toujours garder cette caractéristque en tête, car elle est source de problèmes subtiles.

2 Caractères

L'inclusion du type des caractères, char, dans l'ensemble des types entiers est un choix surprenant, et discutable, fait par les concepteurs de Java.

Ce choix est motivé par la norme Unicode, qui a pour but d'associer à tout caractère existant un unique entier positif, appelé son point de code. Par exemple, le caractère Z majuscule de l'alphabet latin a pour point de code l'entier 90. Etant donnée cette correspondance, tout caractère peut être vu comme son point de code Unicode, donc comme un entier.

Dès lors, en Java, toute valeur de type char est considérée comme un entier, et peut être manipulée comme telle, p.ex. au moyen d'opérations arithmétiques. Ainsi, l'extrait de programme ci-dessous est valide :

char z = 'Y' + 1;
int i = 'Z';
System.out.println(z + "=" + i); // affiche Z=90

Malheureusement, la norme Unicode a évolué depuis la conception de Java, et la correspondance entre une valeur Java de type char et un point de code Unicode n'est plus aussi simple qu'initialement, comme nous le verrons ultérieurement.

3 Représentation des entiers

En mémoire, les entiers Java sont représentés par des vecteurs de bits (pour binary digit, soit chiffre binaire) de taille fixe : 8 bits pour byte, 16 pour short et char, 32 pour int, et 64 pour long. Ces vecteurs de bits sont interprétés comme des nombres exprimés en base 2. Par exemple, le vecteur de huit bits 00001100 est interprété comme l'entier douze :

bit no 7 6 5 4 3 2 1 0
valeur 0 0 0 0 1 1 0 0

En effet :

\begin{align*} & 0\cdot 2^7 + 0\cdot 2^6 + 0\cdot 2^5 + 0\cdot 2^4 + 1\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 0\cdot 2^0\\ =\ & 2^3 + 2^2\\ =\ & 8 + 4\\ =\ & 12 \end{align*}

Dans un vecteur de bits interprété comme un entier, tous les bits n'ont pas la même importance :

  • le bit le plus à droite vaut 1 s'il est à 1, 0 sinon,
  • le second bit depuis la droite vaut 2 s'il est à 1, 0 sinon,
  • le troisième bit depuis la droite vaut 4 s'il est à 1, 0 sinon,
  • etc.

De manière générale, le bit à la position n vaut 2n s'il est à 1, 0 sinon. Pour cette raison, le bit le plus à gauche est dit bit de poids (le plus) fort (most-significant bit, ou MSB) tandis que le bit le plus à droite est dit bit de poids (le plus) faible (least-significant bit ou LSB).

3.1 Entiers négatifs

A l'exception du type char, qui ne représente que des valeurs positives, les types entiers de Java peuvent également représenter des valeurs négatives. Comment représenter de telles valeurs négatives sous la forme d'un vecteur de bits ? Plusieurs solutions existent, mais celle qui est utilisée par Java — et de manière presque universelle en informatique — est appelée complément à deux (two's complement).

En complément à deux, la représentation d'un entier négatif s'obtient en inversant les bits de la représentation de sa valeur absolue (0 devient 1, 1 devient 0) puis en ajoutant 1 au résultat. Par exemple, sur 8 bits, l'entier 12 est représenté par 00001100, donc l'entier –12 est représenté par 11110100 : en inversant les bits de 00001100 on obtient 11110011, puis en ajoutant 1 on obtient 11110100.

Le complément à deux a plusieurs propriétés importantes :

  1. les opérations arithmétiques (addition, soustraction, etc.) n'ont pas besoin de traiter les valeurs négatives de manière particulière, tout fonctionne « tout seul »,
  2. le bit de poids fort donne le signe de la valeur : s'il vaut 0, elle est positive ou nulle, s'il vaut 1, elle est négative,
  3. un vecteur de n bits peut représenter :
    • 2n-1 – 1 valeurs strictement positives,
    • 2n-1 valeurs strictement négatives, et
    • zéro (qui n'a qu'une représentation).

Il est important de comprendre que la notion de signe n'est qu'une question d'interprétation. C'est-à-dire qu'un vecteur de bits donné peut être interprété soit comme une valeur non signée (c-à-d non négative), soit comme une valeur signée en complément à deux.

En Java, les valeurs de tous les types entiers sauf char sont interprétées comme des valeurs signées en complément à deux, tandis que les valeurs de type char sont interprétées comme non signées. Ainsi, un vecteur de 16 bits valant tous 1 est interprété comme l'entier -1 si on lui donne le type short, mais comme l'entier 65'535 (216 – 1) si on lui donne le type char, comme l'illustre le programme ci-dessous :

short s = (short)0b11111111_11111111;
char c  = (char) 0b11111111_11111111;
System.out.println((int)s);     // affiche -1
System.out.println((int)c);     // affiche 65535

Les types short et char font tous les deux 16 bits, la seule différence entre les deux étant la manière dont ces bits sont interprétés.

4 Notation des entiers

En Java, les valeurs entières constantes — appelées aussi entiers littéraux (integer literals) — peuvent être écrites en quatre bases : 2 (binaire), 8 (octal), 10 (décimal) et 16 (hexadécimal).

Par défaut, les valeurs entières constantes sont en base 10, par exemple :

int earthRadius = 6371;

Les chiffres d'un entier littéral peuvent être séparés par des caractères souligné (_) pour faciliter la lecture :

int earthRadius = 6_371;

Les entiers littéraux ont toujours le type int, sauf si on leur ajoute le suffixe l ou L, auquel cas ils ont le type long :

long earthPopulation = 7_130_000_000L;

Aucun suffixe similaire n'existe pour byte ou short, il faut donc recourir à des conversions, implicites ou explicites.

Les entiers littéraux peuvent être écrits en binaire, il suffit pour cela de leur ajouter le préfixe 0b ou 0B :

int twelve = 0b1100; // vaut 12
int maxInt = 0b01111111_11111111_11111111_11111111;
long twelveAsLong = 0b1100L; // vaut 12

Attention, ces entiers littéraux binaires peuvent être négatifs même en l'absence de signe de négation (-) :

// vaut -1
int minusOne = 0b11111111_11111111_11111111_11111111;

et, dès lors, positifs même en présence d'une négation :

// vaut 1
int plusOne = -0b11111111_11111111_11111111_11111111;

Les entiers littéraux peuvent être écrits en hexadécimal (base seize) avec le préfixe 0x ou 0X. Les lettres A à F — minuscule ou majuscule — sont utilisées pour représenter les chiffres après 9 :

int twelve = 0xC;                       // vaut 12
int thirtyTwo = 0x20;                   // vaut 32
int x = 0xDEAD_BEEF;                    // vaut -559038737
long minusOne = 0xFFFF_FFFF_FFFF_FFFFL; // vaut -1 (long)

L'intérêt de la notation hexadécimale comparé à la notation décimale est que chaque chiffre représente exactement quatre bits.

Finalement, les entiers littéraux peuvent être écrits en octal (base huit) grâce au préfixe 0. Cette notation, héritée du langage C, est totalement anachronique mais il faut néanmoins la connaître car elle peut engendrer des surprises étant donné le préfixe utilisé ! En effet, mettre un (ou plusieurs) 0 en tête d'un entier littéral change sa base, donc généralement sa valeur. Par exemple :

int thirty    =  30; // vaut 30
int notThirty = 030; // vaut 24 (!)

5 Opérations arithmétiques

Les opérations arithmétiques de base sont disponibles sur les entiers, à savoir :

  • l'addition : x + y,
  • la soustraction : x - y,
  • la multiplication : x * y,
  • la division entière : x / y,
  • le reste de la division entière, souvent appelé modulo : x % y.

La plupart de ces opérations peuvent produire des valeurs non représentables dans le type entier concerné. On dit alors qu'il y a dépassement de capacité (overflow).

En cas de dépassement de capacité, la valeur résultant de l'opération arithmétique est simplement tronquée au nombre de bits du type du résultat. Dès lors, cette valeur est incorrecte d'un point de vue mathématique. En particulier, notez qu'en raison de l'utilisation du complément à deux, il est même possible que le résultat n'ait pas le bon signe !

Les dépassements de capacité sont la source de nombreux problèmes de sécurité, particulièrement dans des langages non sûrs comme C et C++.

Le comportement en cas de dépassement de capacité peut s'illustrer en calculant la somme de 120 (01111000 en binaire) et 10 (00001010) sur des entiers de type byte (8 bits) :

bit 7 6 5 4 3 2 1 0
retenue 1 1 1 1        
120 0 1 1 1 1 0 0 0
10 0 0 0 0 1 0 1 0
somme 1 0 0 0 0 0 1 0

En d'autres termes, si on calcule la somme 120 + 10 avec des valeurs de type byte, on obtient –126 (10000010) et pas 130 ! Le même genre de problèmes existe avec les autres types entiers, mais pour des valeurs plus grandes.

Parmi les problèmes moins évidents dus aux dépassement de capacité, on peut en citer deux :

  1. la valeur absolue d'un entier Java peut être négative — si cet entier est la plus petite valeur entière représentable, p.ex. 0x80000000 pour le type int,
  2. la négation (-) peut se comporter en Java comme l'identité pour une valeur non nulle — là aussi, cela n'est vrai que pour la plue petite valeur entière représentable.

Il est bon de garder cela à l'esprit, surtout lorsqu'on écrit du code sensible.

Un exemple de problème subtile dû aux dépassements de capacité apparaît dans la méthode d'inversion de comparateur suivante :

<T> Comparator<T> invComp(Comparator<T> c) {
  return (o1, o2) -> -c.compare(o1, o2); // FAUX !
}

Cette méthode fonctionne toujours, sauf dans le cas où le comparateur c retourne 0x80000000, la plus petite valeur de type int représentable, qui n'a pas d'équivalent positif. La manière correcte d'inverser un comparateur est donc :

<T> Comparator<T> invComp(Comparator<T> c) {
  return (o1, o2) -> c.compare(o2, o1);
}

6 Opérations bit à bit

En plus des opérations arithmétiques, Java offre ce que l'on appelle des opérations bit à bit (bitwise operations), travaillant sur les vecteurs de bits représentant les entiers.

Ces opérations adoptent un point de vue différent des entiers que les opérations arithmétiques, puisqu'elles les considèrent comme des vecteurs de bits et pas comme les entiers qu'ils représentent.

Dès lors, initialement en tout cas, il est préférable de ne pas mélanger ces deux points de vue, et de traiter les entiers Java soit comme des entiers mathématiques — auxquels on applique des opérations arithmétiques — soit comme des vecteurs de bits — auxquels on applique des opérations bit à bit.

En Java, les opérations bit à bit sont au nombre de sept :

  • l'inversion (ou complément) : ~x,
  • la conjonction (et) bit à bit : x & y,
  • la disjonction (ou) bit à bit : x | y,
  • la disjonction exclusive (ou exclusif) bit à bit : x ^ y,
  • le décalage à gauche : x << y,
  • le décalage à droite arithmétique : x >> y,
  • le décalage à droite logique : x >>> y.

6.1 Inversion

L'inversion ou complément parallèle ou bit à bit (bitwise complement), noté ~, inverse chaque bit de son opérande.

Par exemple, ~0b11110000 vaut 0b00001111.

Etant donné que les valeurs négatives sont représentées au moyen du complément à deux, l'inversion et la négation sont liées par l'égalité suivante, valable pour toute valeur x d'un type entier, char excepté :

-x == ~x + 1

6.2 Opérateurs parallèles

Les opérateurs binaires parallèles ou bit à bit (binary bitwise operators) &, | et ^ appliquent la même opération à chacun des bits de leurs opérandes. Ces opérations sont définies par les tables ci-dessous.

Sorry, your browser does not support SVG.

Figure 1 : Tables de vérité des opérateurs bit à bit

Par exemple, appliquées aux opérandes 11110000 et 00111100, ces trois opérations produisent les résultats illustrés dans la figure suivante.

Sorry, your browser does not support SVG.

Figure 2 : Exemple des opérateurs bit à bit

6.3 Décalages

La valeur de l'expression x << y est obtenue par décalage vers la gauche, de y positions, des bits de x.

Par exemple, 0b00001100 << 3 vaut 0b01100000, car tous les bits de la première opérande sont décalés de 3 positions sur la gauche, les trois de poids fort sont perdus, et trois bits nuls sont insérés à droite. Cela est illustré sur la figure ci-dessous.

Sorry, your browser does not support SVG.

Figure 3 : Décalage à gauche de 3 positions

Attention : seuls les 5 (respectivement 6) bits de poids faible de la seconde opérande sont pris en compte pour déterminer l'amplitude du décalage lors du décalage d'une valeur de type int (respectivement long).

Les deux opérateurs de décalage à droite, >> et >>>, sont similaires à celui de décalage à gauche, mais travaillent dans la direction opposée.

Le décalage dit arithmétique, noté >>, copie le bit de poids fort dans toutes les positions laissées libres par le décalage. Le décalage dit logique, noté >>>, insère quant à lui des bits nuls, comme l'opérateur de décalage à gauche.

Les deux opérateurs de décalage à droite ne diffèrent que pour les valeurs dont le bit de poids fort vaut 1, c-à-d les valeurs représentant des entiers négatifs. Pour de telles valeurs, le décalage arithmétique préserve le signe et produit donc une valeur négative, tandis que le décalage logique produit une valeur positive pour tout décalage d'amplitude non nulle.

6.4 Décalages et multiplications

Un décalage à gauche de n bits est équivalent à une multiplication par 2n, pour la même raison que, en base 10, un décalage à gauche de n positions des chiffres d'un nombre est équivalent à une multiplication par 10n :

x << n == x * pow(2, n)

pow(2, n) représente 2n.

Un décalage à droite de n bits est équivalent à une division entière par 2n, pour les valeurs non négatives seulement :

x >> n == x / pow(2, n)         // (si x ≥ 0)

Pour les valeurs négatives, les deux expressions diffèrent d'une unité dans certains cas.

6.5 Schémas d'utilisation

Certaines constructions impliquant les opérateurs bit à bit sont fréquemment utiles, et il est donc bon de les connaître. Les plus importantes d'entre elles sont présentées ci-après.

6.5.1 Masques

Il est souvent utile de manipuler un ou plusieurs bits d'un entier sans toucher aux autres. Pour ce faire, on construit tout d'abord un entier — appelé le masque (mask) — dont seuls les bits à manipuler sont à 1. Ensuite, on utilise l'opération bit à bit appropriée (&, | ou ^), appliquée au masque et à la valeur.

Un masque peut soit s'écrire directement sous forme d'entier littéral — généralement en base 2 ou 16 — soit se construire en combinant décalages et disjonctions :

int mask13 = 1 << 13;            // uniquement bit 13
int mask17 = 1 << 17;            // uniquement bit 17
int mask13_17 = mask13 | mask17; // bits 13 et 17

Un masque composé d'une longue séquence de bits à 1 peut s'obtenir en combinant judicieusement un décalage et une soustraction. Par exemple, pour obtenir un masque dont les n bits de poids faible sont à 1, on peut écrire :

int mask = (1 << n) - 1;

6.5.2 Test de bit(s)

Pour tester si un ou plusieurs bits d'un entier sont à 1, on utilise le « et bit à bit » (&) entre le masque et l'entier, puis on regarde si la valeur obtenue est égale au masque.

Par exemple, pour tester si les bits 13 et 17 de l'entier x sont à 1, on écrit :

boolean bits13_17Set = (x & mask13_17) == mask13_17;

Pour tester si tous ces bits sont à 0, on écrit :

boolean bits13_17Cleared = (x & mask13_17) == 0;

Pour tester si au moins l'un de ces bits est à 1, on écrit :

boolean bit13OrBit17Set = (x & mask13_17) != 0;

6.5.3 (Dés)activation de bits

Pour activer (c-à-d mettre à 1) un ou plusieurs bits d'un entier sans toucher aux autres, on utilise le « ou bit à bit » (|) appliqué au masque et à l'entier.

Par exemple, pour mettre à 1 les bits 13 et 17 de l'entier x, on écrit :

int xWithBits13_17Set = x | mask13_17;

Pour désactiver (c-à-d mettre à 0) un ou plusieurs bits d'un entier sans toucher aux autres, on utilise le « et bit à bit » (&) appliqué au complément du masque et à l'entier.

Par exemple, pour mettre à 0 les bits 13 et 17 de l'entier x, on écrit :

int xWithBits13_17Cleared = x & ~mask13_17;

Pour inverser un ou plusieurs bits d'un entier sans toucher aux autres, on utilise le « ou exclusif bit à bit » appliqué au masque et à l'entier.

Par exemple, pour inverser les bits 13 et 17 de l'entier x, on écrit :

int xWithBits13_17Toggled = x ^ mask13_17;

6.5.4 Multiplication et division par une puissance de deux

La multiplication par une puissance de deux peut se faire au moyen d'un décalage à gauche :

x * pow(2, n) == x << n

Pour les valeurs non négatives uniquement, la division par une puissance de deux peut se faire au moyen d'un décalage à droite :

x / pow(2, n) == x >> n         // (si x ≥ 0)

Pour ces mêmes valeurs, le reste de la division par une puissance de deux peut se faire par masquage :

x % pow(2, n) == x & ((1 << n) - 1) // (si x ≥ 0)

Un cas particulier du reste d'une division par une puissance de deux est le test de parité : pour savoir si une valeur est paire (respectivement impaire), il suffit de regarder si son bit de poids faible vaut 0 (respectivement 1). Cela fonctionne également pour les valeurs négatives.

Par exemple, pour tester si l'entier x est pair, on écrit :

boolean isXEven = (x & 1) == 0;

et pour tester s'il est impair :

boolean isXOdd = (x & 1) == 1;

7 Entiers dans l'API Java

La bibliothèque Java contient, dans le paquetage java.lang, une classe pour chaque type d'entier :

Ces classes ont deux buts :

  1. servir de « classes d'emballage » pour la généricité,
  2. offrir, sous forme de méthodes statiques, des opérations sur les valeurs du type qu'elles représentent.

7.1 Taille des types

Chaque classe d'entiers fournit des attributs statiques donnant des informations quant à la taille du type entier correspondant :

  • MIN_VALUE et MAX_VALUE donnent respectivement la plus petite et la plus grande valeur représentable par le type entier,
  • SIZE donne la taille, en bits, du type entier,
  • BYTES donne la taille, en octets, du type entier.

Par exemple, Byte.MIN_VALUE vaut –128, Byte.MAX_VALUE vaut 127, Byte.SIZE vaut 8 et Byte.BYTES vaut 1.

7.2 Conversions de/vers texte

Les classes Integer et Long offrent deux variantes d'une méthode statique permettant de convertir un entier en chaîne de caractères. Par exemple, Integer offre :

Les classes Byte et Short offrent uniquement la seconde variante.

Chaque classe d'entiers offre deux variantes d'une méthode statique permettant de transformer une chaîne en l'entier signé correspondant. Par exemple, Integer offre :

Les classes Byte, Short et Long offrent des méthodes similaires, nommées respectivement parseByte, parseShort et parseLong.

7.3 Comptage de bits

Integer et Long offrent des méthodes statiques permettant de compter certains types de bits. Par exemple, Integer offre :

Les méthodes de Long sont identiques mais prennent un argument de type long.

7.4 Position des bits

Integer et Long offrent des méthodes statiques permettant de déterminer la position de certains bits. Par exemple, Integer offre :

Ainsi :

  • Integer. lowestOneBit(0b1110) == 0b0010
  • Integer.highestOneBit(0b1110) == 0b1000

7.5 Rotation

Les classes Integer et Long offrent chacune des méthodes statique permettant d'effectuer une rotation des bits. Par exemple, Integer offre :

Une rotation est similaire à un décalage, mais les bits qui sont éjectés d'un côté sont réinjectés de l'autre.

7.6 Inversion de bits et octets

Les classes Integer et Long offrent des méthodes statiques permettant d'inverser l'ordre des bits ou des octets d'un entier. Par exemple, Integer offre :

Short offre également reverseBytes.

8 Empaquetage

Etant donné que les entiers sont en réalité des vecteurs de bits, il est assez fréquent de les utiliser pour contenir plusieurs petites valeurs. On dit alors que ces valeurs sont empaquetées (packed) dans un entier.

Par exemple, un entier de type int faisant 32 bits, on peut y stocker 32 valeurs binaires, ou 4 valeurs de 8 bits, etc. Cette technique est souvent utilisée pour représenter les couleurs, exemple qu'il vaut la peine d'examiner en détail.

8.1 Couleurs empaquetées

En informatique, une couleur est souvent représentée par ses trois composantes rouge, verte et bleue, chacune étant un nombre réel compris entre 0 et 1 (inclus).

La manière la plus naturelle de représenter une telle couleur en Java consiste à créer une classe dotée de trois champs de type double (ou float). Bien que naturelle, cette représentation est coûteuse en espace : sachant qu'une valeur de type double fait 8 octets (64 bits), chaque couleur nécessite au moins 3×8 = 24 octets (192 bits), ou la moitié si le type float est utilisé.

Une manière plus compacte, mais moins précise, de représenter une couleur consiste à représenter chacune de ses composantes par un entier de 8 bits — compris entre 0 et 255 — puis à les empaqueter dans un entier de 32 bits. Les 8 bits restants sont soit inutilisés, soit utilisés pour stocker l'opacité de la couleur. De la sorte, une couleur occupe exactement 32 bits au lieu de 192 dans la représentation précédente, un gain appréciable.

Les composantes d'une couleur peuvent être empaquetées de nombreuses manières. Dans ce qui suit, la composante bleue est placée dans les huit bits de poids faible, suivie de la verte puis la rouge. Cette technique d'empaquetage est souvent désignée par l'acronyme RGB.

bits 31 … 24 23 … 16 15 … 8 7 … 0
contenu inutilisés rouge (R) vert (G) bleu (B)

La notation hexadécimale convient assez bien pour écrire directement des couleurs empaquetées de la sorte, car chaque composante occupe exactement deux chiffres hexadécimaux (8 bits). Par exemple 0xFF_00_00 représente un rouge pur (1,0,0).

Le passage d'une couleur exprimée sous la forme de trois composantes réelles comprises entre 0 et 1 à une couleur empaquetée RGB se fait en combinant décalages et « ou » parallèle :

double r = …, g = …, b = …;
int r0 = (int)(r * 255.9999); // 0 ≤ r0 ≤ 255
int g0 = (int)(g * 255.9999); // 0 ≤ g0 ≤ 255
int b0 = (int)(b * 255.9999); // 0 ≤ b0 ≤ 255
int rgb = (r0 << 16) | (g0 << 8) | b0;

Une composante quelconque d'une couleur empaquetée peut être extraite en combinant un décalage avec un masquage. Par exemple, la composante verte peut être obtenue par un décalage à droite de 8 bits suivi d'un masquage pour ne garder que les 8 bits de poids faible :

int rgb = …;
int g0 = (rgb >> 8) & 0xFF;

Cette valeur entière, comprise entre 0 et 255, peut être ramenée à l'intervalle [0;1] par une simple division :

double g = (double)g0 / 255d;

9 Références