Système négabinaire

Les bases numériques négatives ont été découvertes par Vittorio Grünwald (en) dans son travail Giornale di Matematiche di Battaglini, publié en 1885. Grünwald donna des algorithmes pour exécuter les additions, les soustractions, les multiplications, les divisions, les extractions de racines, les tests de divisibilité et les conversions de bases. Les bases négatives furent redécouvertes indépendamment plus tard par Aubrey J. Kempner (en) en 1936 et Zdzisław Pawlak (en) et A. Wakulicz en 1959.

Tout entier relatif peut être écrit de manière unique sous la forme

${\displaystyle \sum _{k=0}^{n}d_{k}(-2)^{k}}$

où chaque chiffre d_k est soit 0 ou 1 et le « bit conducteur » d_n est 1 (à moins que n = 0). Le développement négabinaire d'un entier donné est alors donné par la chaîne :

${\displaystyle d_{n};d_{n-1}...d_{1}d_{0}.}$

Quelques nombres négabinaires ont la même représentation en système binaire. Par exemple,

${\displaystyle 17=2^{4}+2^{0}}$

est représenté par 10001 en binaire et 10001 en négabinaire.

Les nombres allant de –5 à 6 avec leurs développements négabinaires sont :

–5  1111
–4  1100
–3  1101
–2    10
–1    11
 0     0
 1     1
 2   110
 3   111
 4   100
 5   101
 6 11010

Le développement négabinaire d'un nombre peut être trouvé avec une division répétée par –2, en enregistrant les restes non négatifs de 0 ou 1, en concaténant ces restes puis en démarrant avec le dernier. Note : si a / b = c, reste d, alors bc + d = a. Par exemple :

13 / –2 = –6, reste 1
–6 / –2 =  3, reste 0
 3 / –2 = –1, reste 1
–1 / –2 =  1, reste 1
 1 / –2 =  0, reste 1

Par conséquent, le développement négabinaire de 13 est 11101.

Note : les développements négabinaires d'entiers négatifs ont un nombre pair de bits, tandis que les développements négabinaires d'entiers positifs ont un nombre impair de bits.

Pour ajouter deux nombres négabinaires, démarrer avec une retenue 0, et en démarrant à partir du bit de poids faible, ajouter les bits des deux nombres plus la retenue. Le nombre résultant est alors recherché dans la table suivante pour obtenir le bit à écrire dans le résultat, et la retenue suivante :

nombre bit retenue
  –2    0    1 (Note : –2 apparaît seulement pendant la soustraction).
  –1    1    1
   0    0    0
   1    1    0
   2    0   –1
   3    1   –1 (Note : 3 apparaît seulement pendant l'addition).

La deuxième ligne de cette table, par exemple, exprime le fait que –1 = 1 + 1×(–2); la cinquième ligne dit que 2 = 0 + –1×(–2); etc.

Comme exemple, ajouter 1010101 (1 + 4 + 16 + 64 = 85) et 1110100 (4 + 16 – 32 + 64 = 52),

retenue :          1 –1  0 –1  1 –1  0  0  0
premier nombre :         1  0  1  0  1  0  1
deuxième nombre :        1  1  1  0  1  0  0 +
                  --------------------------
nombre:            1 –1  2  0  3 –1  2  0  1
bit (résultat) :   1  1  0  0  1  1  0  0  1
retenue:           0  1 –1  0 –1  1 –1  0  0

donc, le résultat est 110011001 (1 – 8 + 16 – 128 + 256 = 137).

Pour soustraire, multiplier chaque bit du deuxième nombre par –1, et ajouter les nombres, en utilisant la même table que ci-dessus.

Comme exemple, calculer 1101001 (1 – 8 – 32 + 64 = 25) moins 1110100 (4 + 16 – 32 + 64 = 52),

retenue :          0  1 –1  1  0  0  0
premier nombre :   1  1  0  1  0  0  1
deuxième nombre : –1 –1 –1  0 –1  0  0 +
                  --------------------
nombre:            0  1 –2  2 –1  0  1
bit (résultat) :   0  1  0  0  1  0  1
retenue:           0  0  1 –1  1  0  0

donc le résultat est 100101 (1 + 4 – 32 = –27).

Pour rendre négatif un nombre, calculer 0 moins le nombre.

Décaler vers la gauche multiplie par –2, décaler vers la droite divise par –2.

Pour multiplier, multiplier comme en système décimal, mais en utilisant les règles négabinaires pour ajouter la retenue, lorsqu'on ajoute les nombres.

premier nombre :                   1  1  1  0  1  1  0
deuxième nombre :                  1  0  1  1  0  1  1 *
                 -------------------------------------
                                   1  1  1  0  1  1  0
                                1  1  1  0  1  1  0
                          1  1  1  0  1  1  0
                       1  1  1  0  1  1  0
                 1  1  1  0  1  1  0                   +
                 -------------------------------------
retenue:         0 –1  0 –1 –1 –1 –1 –1  0 –1  0  0
nombre:          1  0  2  1  2  2  2  3  2  0  2  1  0
bit (résultat) : 1  0  0  1  0  0  0  1  0  0  0  1  0
retenue :           0 –1  0 –1 –1 –1 –1 –1  0 –1  0  0

Pour chaque colonne, ajouter retenue à nombre, et diviser la somme par –2, pour obtenir la nouvelle retenue, et le bit résultant comme reste.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Negabinary » (voir la liste des auteurs).
• Vittorio Grünwald, Giornale di Matematiche di Battaglini (1885), 203-221, 367
• A. J. Kempner. (1936), 610-617
• Z. Pawlek et A. Wakulicz, Bulletin de l'Académie Polonaise des Sciences, Classe III, 5 (1957), 233-236; Série des sciences techniques 7 (1959), 713-721
• L. Wadel IRE Transactions EC-6 1957, 123
• N. M. Blachman, Communications of the ACM (1961), 257
• IEEE Transactions, 1963, 274-276
• Computer Design Mai 1967, 52-63
• R. W. Marczynski, Annotated History of Computing, 1980, 37-48
• Donald Knuth, The Art of Computer Programming, vol. 2, 3^e éd., p. 204-205