Écrire une fonction en langage python :
Un programme possible :
def listeCompVersEntiers(liste) :
n=len(liste)
s=-2**(n-1)*liste[0]
for j in range(1,n) :
s+=2**(n-1-j)*liste[j]
return s
print(listeCompVersEntiers([1,0,1,0]))
La technique suivante permet, à partir du code en complément à 2 d'un entier n, d'obtenir le code de son opposé.
Exemple.
\( n = 100_{\text{dix}} \).
En complément à 2 sur 8 bits, n a pour écriture n='0110 0100'.
On prend les compléments à 1 bit à bit, on obtient '1001 1011'.
On ajoute 1, on obtient le code de - n = '1001 1100'.
On vérifie effectivement que \( -2^7 + 2^4 + 2^3 +2^2 = -100_{\text{dix}} \)
Le code de n=53 en complément à deux sur huit bits est n='0011 0101'.
Le résultat de l'inversion bit à bit est '1100 1010'.
Ajoutons 1 à ce résultat : -n a pour code '1100 1011'.
On vérifie que \( -2^7 +2^6 + 2^3+ 2^1+2^0 = -53 \).
Le code de n=15 en complément à deux sur huit bits est n='0000 1111'.
Le résultat de l'inversion bit à bit est '1111 0000'.
Ajoutons 1 à ce résultat : -n a pour code '1111 0001'.
On vérifie que \( -2^7 +2^6+2^5+2^4+2^0 = -15 \).
Le code de n=16 en complément à deux sur huit bits est n='0001 0000'.
Le résultat de l'inversion bit à bit est '1110 1111'.
Ajoutons 1 à ce résultat : -n a pour code '1111 0000'.
On vérifie que \( -2^7 +2^6+2^5+2^4 = -16 \).
Partons d'un entier positif A codé en complément à 2 sur n bits par \(0d_{n-2}d_{n-3}\dots d_{0} \). On a donc \[ A = 0\times 2^{n-1} + d_{n-2}\times 2^{n-2} + d_{n-3} \times 2^{n-3} +\dots + d_{0}\times 2^0 \] Par complément à 1 bit à bit, on obtient une représentation de l'entier : \[ B = -1 \times 2^{n-1} + (1-d_{n-2})\times 2^{n-2} +(1- d_{n-3}) \times 2^{n-3} +\dots +(1- d_{0})\times 2^0 \] ce qui donne \[B = -1 \times 2^{n-1} + \sum_{j=0}^{n-2} 2^j - \left( d_{n-2}\times 2^{n-2} + d_{n-3} \times 2^{n-3} +\dots + d_{0} \times 2^0 \right) \] soit \[B = -1 \times 2^{n-1} + \left( 2^{n-1} -1 \right) - A \] c'est à dire \[ B= -1-A\] Si l'on ajoute 1 au résultat, on obtient bien \( -A \).
De la même façon, partons d'un entier négatif A codé en complément à 2 sur n bits par \(1d_{n-2}d_{n-3}\dots d_{0} \). On a donc \[ A = -1\times 2^{n-1} + d_{n-2}\times 2^{n-2} + d_{n-3} \times 2^{n-3} +\dots + d_{0}\times 2^0 \] Par complément à 1 bit à bit, on obtient une représentation de l'entier : \[ B = 0 \times 2^{n-1} + (1-d_{n-2})\times 2^{n-2} +(1- d_{n-3}) \times 2^{n-3} +\dots +(1- d_{0})\times 2^0 \] ce qui donne \[B = \sum_{j=0}^{n-2} 2^j - \left( d_{n-2}\times 2^{n-2} + d_{n-3} \times 2^{n-3} +\dots + d_{0} \times 2^0 \right) \] soit \[B = 2^{n-1} -1 - \left( d_{n-2}\times 2^{n-2} + d_{n-3} \times 2^{n-3} +\dots + d_{0} \times 2^0 \right) \] c'est à dire \[ B= -1-A\] Si l'on ajoute 1 au résultat, on obtient bien \( -A \).
L'entier le plus petit en complément à 2 sur n bits, représenté par '10...0' et valant \( -2^{n-1}\) a un opposé qui n'a pas de représentation dans ce codage.
La méthode exposée ne peut donc pas fonctionner dans ce cas ! La technique exposée redonne en fait l'entier lui-même.
Soit x un entier. Notons a l'entier obtenu par complément à 1 bit à bit (chaque 1 de l'écriture complément à deux de x est un 0 dans l'écriture de a, chaque 0 dans l'écriture de x est un 1 dans celle de a).
Pour illustrer plaçons nous dans le cas d'une écriture sur 8 bits.
Exemple 1
Exemple 2
Dans tous les cas, on constate aisément que x + a s'écrit uniquement avec des 1.
Dans les deux exemples ci-dessus (écriture sur 8 bits), x+a a pour écriture 1111 1111.
Or l'entier qui ne s'écrit qu'avec des 1 en écriture complément à 2 est l'entier \( -1 \).
Nous avons donc \(x+a = -1\), soit \( a+1 = -x \).
On dispose d'une représentation en complément à deux sur 8 bits d'un entier. On aimerait connaître sa représentation en complément à deux sur 16 bits. Comment procéder ?
Les 7 bits de poids les plus faibles sont recopiés tels quels sur les 7 bits de poids les plus faibles.
Le bit de poids fort (MSB) est recopié sur les 9 bits de poids les plus forts.
\( n = 2_{\text{dix}} \).
\( n = -2_{\text{dix}} \).
L'application de la méthode donne l'écriture 1111 1111 1010 1010.
L'application de la méthode donne l'écriture 0000 0000 0110 1010.
Le cas d'un nombre positif (bit de poids fort à 0) est évident : la somme des puissances de deux associée aux deux écritures est la même sur 8 bits et sur 16 bits.
Pour le cas d'un négatif, il suffit de remarquer l'égalité : \[ -2^{15}+2^{14}+2^{13}+2^{12}+2^{11}+2^{10}+2^{9} = -2^{9} \]
La méthode se généralise sans problème pour passer à 32 bits ou à 64 bits.