Systèmes de numération

L'accent de ce site s'écrit #4f46e5. Trois octets : un peu de rouge, un peu de vert, beaucoup de bleu. Une adresse réseau s'écrit 192.168.1.1, un masque /24, et la mémoire d'un programme qui plante s'affiche en colonnes de 0x7ffd3a20. Aucune de ces notations n'est décorative : elles disent toutes la même chose, un nombre, dans la base qui rend ce nombre lisible.

Une machine ne connaît qu'un alphabet à deux lettres. Tout ce que ce cours étudiera — instructions, adresses, images, sons — est une suite de zéros et de uns. Ce premier chapitre apprend à lire cette suite, à la traduire, et à y calculer. C'est le socle : le complément à deux du chapitre 2, les tables de vérité du chapitre 3 et les modes d'adressage du chapitre 6 sont tous écrits dans cette langue.

Compter, c'est pondérer

Notre système décimal n'a rien d'évident, et le comprendre en tant que système est ce qui permet d'en changer. Écrire 3705, c'est écrire une somme :

13705 = 3 × 10³  +  7 × 10²  +  0 × 10¹  +  5 × 10⁰2     = 3000     +  700      +  0        +  5

Deux ingrédients seulement. Une base $b$ — ici dix — qui fixe le nombre de chiffres disponibles, de $0$ à $b-1$. Et une position, qui donne à chaque chiffre son poids : une puissance de la base, croissante de droite à gauche à partir de $b^0$.

Rien dans cette mécanique n'impose $b = 10$. Le choix de dix est anatomique, pas mathématique. En base $b$ quelconque, un nombre écrit $d_{n-1} \dots d_1 d_0$ vaut :

Et la propriété qui servira partout : avec $n$ chiffres en base $b$, on écrit exactement $b^n$ valeurs différentes, de $0$ à $b^n - 1$. Huit chiffres binaires donnent $2^8 = 256$ valeurs, donc de 0 à 255 — le 255 des masques réseau et des composantes de couleur n'est pas un nombre rond arbitraire, c'est la dernière valeur qui tient sur un octet.

Trois bases, trois raisons

Le cours n'en emploiera que trois, et chacune existe pour une raison distincte.

La base 2 est la seule que le matériel connaisse. Un fil est sous tension ou ne l'est pas ; un transistor conduit ou bloque. Deux états discernables de façon fiable — trois seraient techniquement possibles et le sont si peu qu'on n'en fait pas d'ordinateurs. Le chiffre binaire s'appelle un bit (binary digit).

La base 16, dite hexadécimale, est une commodité d'écriture pour les humains. Ses chiffres vont de 0 à 9 puis A à F, où A vaut 10 et F vaut 15. Son intérêt tient à une coïncidence : $16 = 2^4$, donc un chiffre hexadécimal vaut exactement quatre bits. Un octet s'écrit sur deux caractères au lieu de huit, sans le moindre calcul.

La base 8, octale, joue le même rôle avec $8 = 2^3$ : un chiffre pour trois bits. On la rencontre surtout dans les permissions Unix — le chmod 755 du cours de systèmes est un nombre octal, trois groupes de trois bits.

Retenez la dernière ligne : FF = 255 = un octet plein. Elle revient constamment.

Convertir dans les deux sens

Quatre procédés suffisent, et il faut les avoir tous automatisés.

Base $b$ → décimal : la somme pondérée. On applique la définition. Pour 1011₂ : $1{\times}8 + 0{\times}4 + 1{\times}2 + 1{\times}1 = 11$. Pour 2AF₁₆ : $2{\times}256 + 10{\times}16 + 15 = 687$.

En pratique on emploie le schéma de Horner, qui évite de calculer les puissances : partir de 0, et pour chaque chiffre de gauche à droite, multiplier l'accumulateur par la base puis ajouter le chiffre. Pour 2AF₁₆ : $0{\times}16+2 = 2$, puis $2{\times}16+10 = 42$, puis $42{\times}16+15 = 687$. Trois multiplications, aucune puissance.

Décimal → base $b$ : les divisions successives. On divise par la base, on note le reste, on recommence sur le quotient jusqu'à zéro. Les restes, lus de bas en haut, donnent l'écriture.

1Convertir 214 en binaire2 3214 ÷ 2 = 107  reste 0   ← bit de poids faible4107 ÷ 2 =  53  reste 15 53 ÷ 2 =  26  reste 16 26 ÷ 2 =  13  reste 07 13 ÷ 2 =   6  reste 18  6 ÷ 2 =   3  reste 09  3 ÷ 2 =   1  reste 110  1 ÷ 2 =   0  reste 1   ← bit de poids fort11 12Lecture de bas en haut : 11010110

L'erreur de débutant est de lire les restes de haut en bas. Le contrôle est immédiat : le premier reste obtenu est celui de la division par 2, donc il vaut 1 si et seulement si le nombre est impair — c'est forcément le bit le plus à droite.

Binaire ↔ hexadécimal : le découpage. Aucune arithmétique. On groupe les bits par quatre en partant de la droite, en complétant par des zéros à gauche si besoin, et on traduit chaque groupe.

111010110  →  1101 | 0110  →  D | 6  →  0xD620x4F46E5  →  0100 1111 0100 0110 1110 0101

Avec l'octal, même chose par groupes de trois. Et pour passer de l'hexadécimal à l'octal, on transite par le binaire : il n'existe pas de raccourci direct, $16$ et $8$ n'étant pas puissances l'une de l'autre.

Calculer en binaire

L'addition binaire tient en quatre lignes, dont la dernière est la seule à retenir :

10 + 0 = 020 + 1 = 131 + 0 = 141 + 1 = 0  avec une retenue de 1 sur la colonne suivante

C'est exactement l'addition posée de l'école primaire, avec une retenue qui se déclenche à 2 au lieu de 10. Et c'est aussi, littéralement, le circuit du chapitre 4 : la colonne « somme » est un OU exclusif, la colonne « retenue » est un ET.

1   1 1 1        ← retenues2   0 1 0 1 1    (11)3 + 0 0 1 1 1    ( 7)4 ───────────5   1 0 0 1 0    (18)

La multiplication est plus simple qu'en décimal, parce que la table de multiplication binaire ne contient que des 0 et des 1 : chaque ligne du produit posé est soit une copie décalée du premier facteur, soit une ligne de zéros. D'où un fait qui servira au chapitre 6 : multiplier par 2 revient à décaler tous les bits d'un rang vers la gauche, diviser par 2 à décaler vers la droite. Un processeur qui décale plutôt que de multiplier gagne beaucoup de temps, et un compilateur remplace systématiquement x * 8 par un décalage de 3.

La soustraction binaire posée existe, avec ses emprunts. On ne l'enseignera pas : le chapitre 2 montrera qu'aucune machine ne l'utilise. Elles additionnent l'opposé, et c'est tout l'intérêt du complément à deux.

Bit, octet, mot

Le bit est l'unité. Il ne se manipule presque jamais seul.

L'octet (byte) est le groupe de 8 bits, et l'unité d'adressage de toutes les machines courantes : la mémoire est un tableau d'octets, et chaque octet a une adresse. Un octet code $2^8 = 256$ valeurs.

Le mot (word) est la quantité que le processeur traite en une opération : 32 ou 64 bits aujourd'hui. C'est aussi, en général, la largeur des registres et du bus de données du chapitre 5. Attention au faux ami : la taille du mot dépend de la machine, celle de l'octet non.

Dernier point, source d'une confusion tenace. Les préfixes du système international valent mille : un kilooctet (ko) vaut $10^3 = 1000$ octets. Les préfixes binaires valent 1024 : un kibioctet (Kio) vaut $2^{10} = 1024$ octets. L'écart est de 2,4 % au kilo et grimpe à 7,4 % au téra — c'est toute la différence entre le disque « 1 To » du fabricant et les « 931 Gio » qu'affiche le système, et cela n'a rien d'une escroquerie : ce sont deux unités différentes portant des noms trop proches.

À vous

L'exercice implémente les deux conversions dans les deux sens, puis vérifie qu'elles sont réciproques sur une série de nombres. C'est le meilleur contrôle qui soit : une conversion juste dans un sens et fausse dans l'autre se repère immédiatement.

Attention au piège volontaire du squelette : les restes des divisions successives doivent être lus de bas en haut, et le code fourni les concatène dans le mauvais ordre.

const CHIFFRES = "0123456789ABCDEF";

// Base b -> décimal, par le schéma de Horner : on parcourt les chiffres de
// gauche à droite, on multiplie l'accumulateur par la base, on ajoute.
function versDecimal(texte, base) {
  let n = 0;
  for (const c of texte.toUpperCase()) {
    n = n * base + CHIFFRES.indexOf(c);
  }
  return n;
}

// Décimal -> base b, par divisions successives.
function versBase(n, base) {
  if (n === 0) return "0";
  let sortie = "";
  while (n > 0) {
    const reste = n % base;
    sortie = sortie + CHIFFRES[reste];   // ← les restes s'accumulent... dans quel sens ?
    n = Math.floor(n / base);
  }
  return sortie;
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. versBase est fausse : les restes sont lus à l'envers. Corrigez-la.
// 2. Vérifiez que l'aller-retour redonne bien le nombre de départ.

const CAS = [
  { n: 214, base: 2,  attendu: "11010110" },
  { n: 214, base: 16, attendu: "D6" },
  { n: 687, base: 16, attendu: "2AF" },
  { n: 493, base: 8,  attendu: "755" },
  { n: 255, base: 2,  attendu: "11111111" },
  { n: 0,   base: 2,  attendu: "0" },
];

for (const c of CAS) {
  const ecrit = versBase(c.n, c.base);
  const relu = versDecimal(ecrit, c.base);
  const ok = ecrit === c.attendu && relu === c.n ? "  ok" : "  X attendu " + c.attendu;
  console.log(
    String(c.n).padStart(4) + " en base " + String(c.base).padStart(2) +
    " -> " + ecrit.padEnd(10) + " -> " + String(relu).padStart(4) + ok
  );
}

const CHIFFRES = "0123456789ABCDEF";

function versDecimal(texte, base) {
  let n = 0;
  for (const c of texte.toUpperCase()) {
    n = n * base + CHIFFRES.indexOf(c);
  }
  return n;
}

function versBase(n, base) {
  if (n === 0) return "0";
  let sortie = "";
  while (n > 0) {
    // Le reste obtenu est le chiffre de POIDS LE PLUS FAIBLE de ce qui
    // reste : il s'écrit donc à GAUCHE de ce qu'on a déjà produit.
    sortie = CHIFFRES[n % base] + sortie;
    n = Math.floor(n / base);
  }
  return sortie;
}

const CAS = [
  { n: 214, base: 2,  attendu: "11010110" },
  { n: 214, base: 16, attendu: "D6" },
  { n: 687, base: 16, attendu: "2AF" },
  { n: 493, base: 8,  attendu: "755" },
  { n: 255, base: 2,  attendu: "11111111" },
  { n: 0,   base: 2,  attendu: "0" },
];

for (const c of CAS) {
  const ecrit = versBase(c.n, c.base);
  const relu = versDecimal(ecrit, c.base);
  const ok = ecrit === c.attendu && relu === c.n ? "  ok" : "  X attendu " + c.attendu;
  console.log(
    String(c.n).padStart(4) + " en base " + String(c.base).padStart(2) +
    " -> " + ecrit.padEnd(10) + " -> " + String(relu).padStart(4) + ok
  );
}

En travaux pratiques

173 en base 2                173 en base 16
173 / 2 = 86  reste 1        173 / 16 = 10  reste 13 (D)
86 / 2 = 43  reste 0         10 / 16 =  0  reste 10 (A)
43 / 2 = 21  reste 1
21 / 2 = 10  reste 1        lecture à rebours : AD
10 / 2 =  5  reste 0
5 / 2 =  2  reste 1
2 / 2 =  1  reste 0
1 / 2 =  0  reste 1

lecture à rebours : 1010 1101

void convertir(unsigned int n, int base) {
  const char *chiffres = "0123456789ABCDEF";
  char tampon[33];
  int i = 0;

  if (n == 0) { printf("0\n"); return; }

  while (n > 0) {          /* on empile les restes */
      tampon[i++] = chiffres[n % base];
      n /= base;
  }
  while (i > 0)            /* on les dépile : ordre inverse */
      putchar(tampon[--i]);
  putchar('\n');
}

3735928559 en binaire : 1101 1110 1010 1101 1011 1110 1110 1111  (32 caractères)
3735928559 en hexa    : DEADBEEF                                    ( 8 caractères)

1 chiffre hexadécimal = 4 bits, exactement

250 251 252 253 254 255 0 1 2 3

1111 1111   (255)
+ 0000 0001
-----------
10000 0000   ← 9 bits, mais il n'y a que 8 fils
0000 0000   ← ce qui reste après la troncature

unsigned char u = 255; u + 1  →  0      (retour à zéro)
signed   char s = 127; s + 1  →  -128   (retour au minimum)

les deux valent 1000 0000 en mémoire, ou 0000 0000 selon le cas :
les BITS sont identiques, l'INTERPRÉTATION diffère

Ce que la suite en fait

Ce chapitre n'a manipulé que des entiers positifs, et c'est sa limite : rien de ce qui précède ne sait écrire $-5$, ni $3{,}14$, ni la lettre « é ». Le chapitre 2 lève ces trois restrictions, et découvre au passage que chaque codage a un domaine hors duquel il ment silencieusement.

La suite pondérée sert aussi ailleurs qu'en conversion. La somme $\sum d_i 2^i$ est exactement ce que calcule un décodeur au chapitre 4, et le découpage d'une adresse en « numéro de page » et « déplacement » du chapitre 7 n'est rien d'autre qu'une coupure de cette somme en deux morceaux.

À retenir