Jouer avec les négatifs « sans les moins »

Une base de numération est un système permettant de représenter les nombres à l’aide de puissances d’un même nombre. Dans une base donnée, la décomposition de tout entier est unique ; curieusement, cette propriété reste vraie pour des bases de numération négatives.

Le premier à s’être intéressé aux « bases de numération négatives » est le mathématicien italien Vittorio Grünwald. Il fournit en 1885, dans le Giornale di Matematiche di Battaglini, des algorithmes pour effectuer les opérations arithmétiques usuelles. Ces bases sont ensuite redécouvertes en 1936 par le mathématicien britannico-américain Aubrey Kempner, puis en 1959 par les mathématiciens polonais Zdzisław Pawlak et Andrzej Wakulicz.

Zdzisław Pawlak et Andrzej Wakulicz implantent notamment sur les premiers ordinateurs conçus en Pologne, à la fin des années 1950, un système utilisant la base négabinaire, c’est-à-dire la base –2. Cette base supprime le bit réservé au signe du nombre, mais ses opérations arithmétiques sont plus compliquées à mettre en œuvre et ces essais n’ont pas de descendance.

Dans le système négabinaire, $NN$ désigne un entier et $a_{1}a\_1$, $a_{2}a\_2$, $a_{3}a\_3$, … désignent des bits valant chacun 0 ou 1. L’entier se décompose en puissances de –2 : $$N=a_1\times (\text{–}2{)}^0+a_2\times (\text{–}2{)}^1+a_3\times (\text{–}2{)}^2+a_4\times (\text{–}2{)}^3+\dots N\; =\; a\_1\; \backslash times\; (–2)^0\; +\; a\_2\; \backslash times\; (–2)^1\; +\; a\_3\; \backslash times\; (–2)^2\; +\; a\_4\; \backslash times\; (–2)^3\; +\; \dots$$ Un tableau de conversion des entiers de –5 à 5 peut être dressé.

Les nombres strictement négatifs s’écrivent tous avec un nombre pair de chiffres, tandis que les nombres positifs s’écrivent avec un nombre impair de chiffres.

Seuls les nombres positifs égaux à une somme de puissances de 2 distinctes dont les exposants sont tous pairs, comme 0, 1, 4, 5, 16, 17, 20 et 21, ont la même écriture en binaire et en négabinaire. Pour obtenir les opposés de ces nombres strictement positifs, on ajoute simplement un 1 devant leur écriture négabinaire : $$\text{–}{2}^{2n}=\text{–}{2}^{2n+1}+2^{2n},–2^\{2n\}\; =\; –2^\{2n+1\}\; +\; 2^\{2n\},$$ où $nn$ désigne un entier naturel.

Pour convertir en négabinaire un nombre $NN$ écrit en base 10, où $NN$ désigne l’entier à convertir, on le divise successivement par –2 et on lit les restes dans l’ordre inverse de leur obtention. Chaque reste doit être égal à 0 ou +1. Ainsi, la division de –127 par –2 donne 64 avec pour reste +1, et non 63, qui correspondrait à un reste égal à –1.

Pour les entiers positifs, on peut convertir directement l’écriture binaire en négabinaire. Prenons l’exemple de 235, qui s’écrit 11101011 en binaire.

On vérifie que $$235=2^8\text{–}{2}^5+2^4\text{–}{2}^3+2^2\text{–}{2}^1+2^0\mathrm{.}235\; =\; 2^8\; –\; 2^5\; +\; 2^4\; –\; 2^3\; +\; 2^2\; –\; 2^1\; +\; 2^0.$$ En partant de la droite dans l’écriture binaire, chaque case de rang pair contenant 1 entraîne l’ajout de 1 dans la case immédiatement située à gauche, avec retenue et report éventuel si celle-ci contient déjà un 1.

Pour obtenir l’écriture négabinaire de l’opposé d’un nombre strictement positif, on applique la procédure illustrée ci-dessous.

On soustrait l’écriture négabinaire du nombre positif au nombre 100…00, qui comporte un chiffre de plus et est constitué d’un seul chiffre 1 suivi de zéros, puis on ajoute un 1 devant l’écriture du résultat. On vérifie que $$\text{–}235=\text{–}{2}^9+2^8+2^4+2^2+2^0\mathrm{.}–235\; =\; –2^9\; +\; 2^8\; +\; 2^4\; +\; 2^2\; +\; 2^0.$$

La base négaternaire, c’est-à-dire la base –3, fonctionne de la même façon avec les puissances successives de –3.