Comme nous l'avons vu précédemment, il est assez facile de représenter une valeur binaire (0/1, vrai/faux) à l'aide de tensions électriques, et de construire des circuits qui calculent des fonctions logiques ou arithmétiques. La base 2 est donc naturellement utilisée pour l'arithmétique dans les ordinateurs.

Les entiers non signés

Un entier {$n$} représenté sur {$k$} chiffres dans une base quelconque {$b$} a pour forme : {$$n = a_{k-1}a_{k-2}\dots a_1a_0 = \sum_{i=0}^{k-1}a_i b^i$$}

En base 10, l'entier {$421_{10}$} vaut bien {$4\times 10^2+2\times 10^1+1\times 10^0 = 400+20+1$}.

En binaire, le même entier est représenté par {$110100101_2 = 2^8+2^7+2^5+2^2+2^0 = 256+128+32+4+1$}.

En utilisant au plus {$k$} chiffres, on peut représenter les entiers de l'intervalle {$[0, 2^k-1]$}. La somme de deux nombres de {$k$} chiffres est dans l'intervalle {$[0, 2^k]$} et est donc représentable sur {$k+1$} chiffres. Si le nombre de chiffre {$k$} est fixé, par exemple par le nombre de bascules utilisées pour stocker les nombres, le résultat d'une addition ne pourra donc pas toujours être représenté avec le même nombre de chiffres que celui des opérandes. Si le résultat est trop grand, on aura une retenue (carry) qui est la valeur du bit de poids fort du résultat. Par exemple, pour {$k=4$}, considérons la somme de {$5_{10}=0101_{2}$} et de {$11_{10}=1011_2$} :

{$\begin{array}{rrrrr} & 0& 1& 0& 1\cr & 1& 0& 1& 1\cr \scriptscriptstyle 1& \scriptscriptstyle 1& \scriptscriptstyle 1& \scriptscriptstyle 1& \cr \hline 1& 0& 0& 0& 0 \end{array}$}

Le résultat {$16_{10}= 10000_{2}$} n'est pas représentable sur 4 bits, on obtient donc une somme nulle et une retenue.

Représentation en complément à 2 des entiers signés

Pour représenter des entiers signés, on utilise le plus souvent le complément à 2 : un entier positif {$n$} est représenté en base 2 comme vu précédemment, l'entier négatif {$-n$} est représenté par {$2^k-n$}. Un nombre est considéré comme positif si son bit de poids fort est nul, et négatif si son bit de poids fort est 1. Par exemple, pour {$k=4$}, 0101 est la représentation d'un nombre positif car son bit de poids fort est nul. Il s'agit donc de la représentation de l'entier 5. Dans les mêmes conditions, 1010 est la représentation d'un nombre négatif car son bit de poids fort est 1. Il s'agit donc de la représentation de l'opposé de {$2^4-(8+2) = 16-10 = 6$}, donc celle de {$-6$}.

En complément à 2 sur {$k$} bits, on peut donc représenter les entiers de l'intervalle {$[-2^{k-1}, 2^{k-1}-1]$}. Cet intervalle n'est pas symétrique par rapport à zéro. Ceci est dû au fait qu'en complément à deux, il n'y a qu'une seule représentation de 0 puisque {$2^k-0 = 2^k$} qui donne 0 sur {$k$} bits puisqu'on travaille modulo {$2^k$}. Le nombre d'entiers représentables étant pair (c'est {$2^k$}), il reste un nombre impair de représentations pour les nombres non nuls, qui ne peuvent donc pas être réparties également entre les nombres positifs et les nombres négatifs. La représentation de l'opposé de {$2^{k-1}$} est {$2^k-2^{k-1} = 2^{k-1}$}. Il s'agit donc d'un nombre négatif (son bit de poids fort est 1) dont l'opposé, positif, n'est pas représentable en complément à 2 sur {$k$} bits.

Il existe un moyen simple de calculer le complément à 2 d'un entier : il suffit d'inverser tous ses bits et d'ajouter 1 au résultat. En effet : {$$2^k-\sum_{i=0}^{k-1}a_i 2^i = \left(1+\sum_{i=0}^{k-1}2^i\right)-\sum_{i=0}^{k-1}a_i 2^i = 1+\sum_{i=0}^{k-1}2^i-a_i 2^i = 1+\sum_{i=0}^{k-1}(1-a_i) 2^i$$}

Les opérations sur les entiers représentés en binaire s'appliquent également aux entiers représentés en complément à 2. En représentant {$-b$} par {$2^k-b$}, {$a+(-b)$} devient {$a+2^k-b = 2^k - (b-a)$}, qui est la représentation en complément à 2 de l'opposé de {$b-a$}, c'est-à-dire de {$a-b$}. De même, {$(-a)+(-b)$} se calcule avec {$2^k-a+2^k-b = 2^{k+1}-(a+b)$}. Le calcul se faisant modulo {$2^k$}, ceci est égal à {$2^k-(a+b)$} qui est la représentation en complément à 2 de l'opposé de {$a+b$}, c'est-à-dire {$-a-b$}. Ceci n'est toutefois vrai que si le résultat est représentable en complément à 2 sur {$k$} bits. Le calcul se faisant modulo {$2^k$}, la présence d'une retenue non nulle n'est pas nécessairement le signe d'un débordement. Par exemple, pour faire la somme de -5 et de -2, on commence par coder 5 en binaire : 0101. Le complément à 2 vaut : 1011. De même pour -2 = 1110. On pose l'addition :

{$\begin{array}{rrrrr} & 1& 0& 1& 1\cr & 1& 1& 1& 0\cr \scriptscriptstyle 1& \scriptscriptstyle 1& \scriptscriptstyle 1& & \cr \hline & 1& 0& 0& 1 \end{array}$}

Il y a une retenue, mais le résultat est correct car 1001 est la représentation en complément à 2 sur 4 bits de -0111 = -7 qui est bien la somme de -2 et de -5.

Un critère simple pour détecter les débordements est le suivant :

• Si la somme de deux nombres positifs donne un résultat négatif, il y a débordement.
• Si la somme de deux nombres négatifs donne un résultat positif, il y a débordement.
• Dans les autres cas, il n'y a pas débordement, et la somme de deux nombres de signes opposés ne provoque jamais de débordement.

Ce critère peut également être obtenu en comparant la retenue finale à la retenue propagée sur les bits de poids fort. Si les deux sont égales, il n'y a pas débordement, sinon, il y a débordement. Les circuits qui effectuent les opérations arithmétiques en complément à deux fournissent en général deux indicateurs :

• C (carry) est la retenue finale, utile pour savoir s'il y a débordement quand on travaille en non signé.
• V (oVerflow) qui est le OU exclusif de la retenue finale et de la retenue propagée sur les bits de poids fort. V vaut donc 1 quand ces deux retenues diffèrent, et indique donc un débordement quand on travaille en complément à deux.