Binary arithmetic and signed integers · Arithmétique binaire et entiers signés
| English | Français |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | débordement |
| two's complement/tuːz ˈkɒmplɪmənt/ | complément à deux |
| register/ˈredʒɪstə/ | registre |
| sign bit/saɪn bɪt/ | bit de signe |
| most significant bit/məʊst sɪɡˈnɪfɪkənt bɪt/ | bit de poids fort |
| one's complement/wʌnz ˈkɒmplɪmənt/ | complément à un |
| Binary Coded Decimal/ˈbaɪnəri ˈkəʊdɪd ˈdesɪml/ | Decimal Binaire Codé (BCD) |
The bank that lost a day
- On 1 September 1983 the Vancouver Stock Exchange index stood at 524.811. It had opened at 1000 twenty-two months earlier, and the market had risen the whole time.
- The program recalculated the index after every trade, truncating rather than rounding each time. Each truncation lost a fraction of a point. Three thousand trades a day did the rest.
- When it was recomputed properly the index was 1098.892: the arithmetic, not the market, had halved it.
- Arithmetic on a fixed number of bits is not the arithmetic you learned at school. This lesson is binary addition, overflow 溢出, subtraction by two's complement 补码, signed integers, and BCD.
La banque qui a perdu un jour
- Le 1 septembre 1983, l'indice de la Bourse de Vancouver s'établissait à 524.811. Il avait ouvert à 1000 vingt-deux mois plus tôt, et le marché avait augmenté continuellement.
- Le programme recalculait l'indice après chaque opération, tronquant au lieu d'arrondir à chaque fois. Chaque troncature perdait une fraction de point. Trois mille opérations par jour firent le reste.
- Lorsqu'il a été recalculé correctement, l'indice était 1098.892 : c'est l'arithmétique, et non le marché, qui l'avait divisé par deux.
- L'arithmétique sur un nombre fixe de bits n'est pas celle apprise à l'école. Cette leçon porte sur l'addition binaire, le débordement 溢出, la soustraction par complément à deux 补码, les entiers signés et le BCD.
Binary addition
- Add column by column from the right, carrying into the next column, exactly as in denary.
- The rules: $0 + 0 = 0$; $0 + 1 = 1$; $1 + 1 = 10$, write 0 and carry 1; $1 + 1 + 1 = 11$, write 1 and carry 1.
0101$+$0011$=$1000, that is $5 + 3 = 8$.
Same method as denary, only two digits to carry between
Addition binaire
- Additionnez colonne par colonne de droite à gauche, en reportant vers la colonne suivante, exactement comme en dénaire.
- Les règles : $0 + 0 = 0$ ; $0 + 1 = 1$ ; $1 + 1 = 10$, écrivez 0 et reportez 1 ; $1 + 1 + 1 = 11$, écrivez 1 et reportez 1.
0101$+$0011$=$1000, soit $5 + 3 = 8$.
Même méthode qu'en dénaire, seulement deux chiffres à reporter entre colonnes
Binary & signed integers · Binaire & entiers signés
byte = Σ place values · octet = Σ valeurs de position
See how an 8-bit pattern maps to a number (and how it would overflow past 255). · Voir comment un motif de 8 bits se mappe sur un nombre (et comment il déborderait au-delà de 255).
Add the binary numbers 0101 + 0011. Give the 4-bit result. · Ajoutez les nombres binaires 0101 + 0011. Donnez le résultat sur 4 bits.
$5 + 3 = 8$, which is 1000 in binary. · $5 + 3 = 8$, qui est 1000 en binaire.
Overflow
- Overflow happens when the result of a calculation needs more bits than the register 寄存器 can hold. The carry out of the most significant column is lost, so the stored answer is wrong.
- It is a property of the register width, not of the number 255: in a 16-bit register the same sum is fine.
- In signed arithmetic the tell-tale is a sign bit that flips wrongly: two positives giving a negative, or two negatives giving a positive.
Débordement
- Le débordement survient quand le résultat d'un calcul nécessite plus de bits que le registre 寄存器 ne peut contenir. Le report hors de la colonne de poids fort est perdu, donc la réponse stockée est fausse.
- C'est une propriété de la largeur du registre, pas du nombre 255 : dans un registre 16 bits, la même somme est correcte.
- En arithmétique signée, le signal révélateur est un bit de signe qui change incorrectement : deux positifs donnant un négatif, ou deux négatifs donnant un positif.
Overflow in binary addition means: · Le dépassement de capacité (overflow) dans l'addition binaire signifie :
Overflow occurs when the sum is too large to fit in the available bits; the carry out of the leftmost column is lost. · Le dépassement se produit lorsque la somme est trop grande pour tenir dans les bits disponibles ; le report hors de la colonne de gauche est perdu.
Worked example: name the overflow properly
- Add the 8-bit unsigned integers
10110101and01101100and comment on the result. - The sum is
1 0010 0001, which needs 9 bits. The true result is 289. - Full answer: overflow has occurred, because 289 is larger than the largest value an 8-bit register can hold, 255; the carry out of the most significant bit is lost, so the stored result
0010 0001is 33, which is wrong. - The mark is for naming the register width and saying the result cannot be represented in it. "The answer was more than 255" alone does not score.
Exemple résolu : nommer correctement le débordement
- Additionnez les entiers non signés sur 8 bits
10110101et01101100et commentez le résultat. - La somme est
1 0010 0001, ce qui nécessite 9 bits. Le résultat vrai est 289. - Réponse complète : un débordement s'est produit, car 289 est supérieur à la valeur maximale qu'un registre 8 bits peut contenir, 255 ; le report hors du bit de poids fort est perdu, donc le résultat stocké
0010 0001est 33, ce qui est faux. - Le point est attribué pour nommer la largeur du registre et dire que le résultat ne peut y être représenté. « La réponse était supérieure à 255 » seul ne rapporte pas de points.
Two 8-bit unsigned integers are added and the result needs 9 bits. Which is the full-mark explanation? · Deux entiers non signés de 8 bits sont additionnés et le résultat nécessite 9 bits. Quelle est l'explication complétiste ?
Name the register width, say the result cannot be represented in it, and say what happens to the carry. The other options state a symptom without the cause. · Nommez la largeur du registre, indiquez que le résultat ne peut pas y être représenté, et précisez ce qu'il advient du report. Les autres options ne décrivent qu'un symptôme sans la cause.
Subtraction by two's complement
- To calculate $A - B$: form the two's complement of $B$ by inverting every bit and adding 1, add it to $A$, then discard any final carry-out.
- $100 - 30$ in 8 bits: two's complement of
0001 1110is1110 0001inverted, plus 1, so1110 0010. 0110 0100$+$1110 0010$=$1 0100 0110; discard the leading 1 and read0100 0110$= 70$. ✓
Subtraction becomes addition, which is why processors need no subtractor
Soustraction par complément à deux
- Pour calculer $A - B$ : formez le complément à deux de $B$ en inversant tous les bits et en ajoutant 1, ajoutez-le à $A$, puis jetez tout report final.
- $100 - 30$ sur 8 bits : complément à deux de
0001 1110est1110 0001inversé, plus 1, donc1110 0010. 0110 0100$+$1110 0010$=$1 0100 0110; jetez le 1 de tête et lisez0100 0110$= 70$. ✓
La soustraction devient une addition, c'est pourquoi les processeurs n'ont pas besoin d'un soustracteur
What is the 4-bit two's complement of 0011? (invert, then add 1) · Quelle est la valeur en complément à deux sur 4 bits de 0011 ? (inverser, puis ajouter 1)
Invert 0011 → 1100, then add 1 → 1101 (which represents $-3$). · Inverser 0011 → 1100, puis ajouter 1 → 1101 (ce qui représente $-3$).
Put the steps of subtracting B from A by two's complement in order. · Mettez les étapes de la soustraction de B à A par complément à deux dans l'ordre.
Invert, add one, add, discard. The discard is what keeps the answer in the register's width. · Inverser, ajouter un, ajouter, rejeter. Le rejet est ce qui maintient la réponse dans la largeur du registre.
Two's complement signed integers
- In an $n$-bit two's complement number the most significant bit 最高有效位 is the sign bit 符号位: 0 means positive, 1 means negative. Equivalently, the top bit carries a negative place value, $-2^{n-1}$.
- To read a negative number: invert every bit, add 1, then put a minus sign in front.
1011 0100inverts to0100 1011, plus 1 is0100 1100$= 76$, so the value is $-76$. Check by place value: $-128 + 32 + 16 + 4 = -76$. ✓ - For $n$ bits the range is $-2^{n-1}$ to $+2^{n-1} - 1$: 8 bits give $-128$ to $+127$, 12 bits give $-2048$ to $+2047$. The most negative value is a 1 followed by zeros; the most positive is a 0 followed by ones.
11111111 is 255 read one way and −1 read the other
Entiers signés en complément à deux
- Dans un nombre en complément à deux sur $n$ bits, le bit de poids fort 最高有效位 est le bit de signe 符号位 : 0 signifie positif, 1 signifie négatif. Autrement dit, le bit de tête porte une négative valeur de position, $-2^{n-1}$.
- Pour lire un nombre négatif : inversez tous les bits, ajoutez 1, puis placez un signe moins devant.
1011 0100s'inverse en0100 1011, plus 1 donne0100 1100$= 76$, donc la valeur est $-76$. Vérifiez par valeur de position : $-128 + 32 + 16 + 4 = -76$. ✓ - Pour $n$ bits, l'étendue va de $-2^{n-1}$ à $+2^{n-1} - 1$ : 8 bits donnent $-128$ à $+127$, 12 bits donnent $-2048$ à $+2047$. La valeur la plus négative est un 1 suivi de zéros ; la plus positive est un 0 suivi de uns.
11111111 est 255 lu d'une façon et −1 lu de l'autre
Two's complement signed bits · Bits signés en complément à deux
The leftmost bit carries a negative · négative place value. Flip any bit — or hit Negate (invert every bit, then add 1) — and watch the signed value change. · Le bit de gauche porte une valeur de position négative. Changez n'importe quel bit — ou cliquez sur Negate (inversez chaque bit, puis ajoutez 1) — et watch la valeur signée changer.
Read the 8-bit two's complement number 11111101 as a signed denary value. · Lisez le nombre en complément à deux sur 8 bits 11111101 comme une valeur décimale signée.
MSB is 1 (negative). Invert → 00000010, add 1 → 00000011 $= 3$, so the value is $-3$. · MSB = 1 (négatif). Inverser → 00000010, ajouter 1 → 00000011 $= 3$, donc la valeur est $-3$.
What is the largest positive value an 8-bit two's complement number can hold? · Quelle est la plus grande valeur positive qu'un nombre en complément à deux sur 8 bits peut contenir ?
Range is $-2^{7}$ to · à $2^{7}-1$, i.e. $-128$ to · à $+127$. The maximum is 01111111 = 127. · La plage va de $-2^{7}$ à $2^{7}-1$, c'est-à-dire $-128$ à $+127$. Le maximum est 01111111 = 127.
Worked example: write −108 in 12 bits
- Start from $+108$ in 12 bits: $108 = 64 + 32 + 8 + 4$, so
0000 0110 1100. - Invert every bit:
1111 1001 0011. Add 1:1111 1001 0100. - Check with place values, where the top bit is worth $-2048$: $-2048 + 1024 + 512 + 256 + 128 + 16 + 4 = -108$. ✓
- The commonest error is sign and magnitude: setting the top bit to 1 and leaving the rest. That is a different, older scheme and scores zero here.
Exemple résolu : écrire −108 sur 12 bits
- Partez de $+108$ sur 12 bits : $108 = 64 + 32 + 8 + 4$, donc
0000 0110 1100. - Inversez tous les bits :
1111 1001 0011. Ajoutez 1 :1111 1001 0100. - Vérifiez avec les valeurs de position, où le bit de tête vaut $-2048$ : $-2048 + 1024 + 512 + 256 + 128 + 16 + 4 = -108$. ✓
- L'erreur la plus courante est le signe et magnitude : mettre le bit de tête à 1 et laisser le reste. C'est un schéma différent, plus ancien, qui rapporte zéro ici.
Write −108 as a 12-bit two's complement number (spaces allowed). · Écrivez −108 en complément à deux sur 12 bits (espaces autorisées).
+108 is 0000 0110 1100; invert to 1111 1001 0011 and add 1. Check: −2048 + 1024 + 512 + 256 + 128 + 16 + 4 = −108. · +108 est 0000 0110 1100 ; inverser donne 1111 1001 0011 et ajouter 1. Vérification : −2048 + 1024 + 512 + 256 + 128 + 16 + 4 = −108.
One's complement
- One's complement 反码 is the older scheme: a negative is made by inverting every bit of the positive, with no add-1 step. $+30$ is
0001 1110, so $-30$ is1110 0001. - Its drawback is two zeros,
0000 0000and1111 1111, which wastes a bit pattern and complicates the arithmetic. - Two's complement has one zero and lets the same adder circuit do subtraction, which is why it won.
Complément à un
- Le complément à un 反码 est l'ancien schéma : un négatif est obtenu en inversant tous les bits du positif, sans étape d'ajout de 1. $+30$ est
0001 1110, donc $-30$ est1110 0001. - Son inconvénient est d'avoir deux zéros,
0000 0000et1111 1111, ce qui gaspille un motif binaire et complique l'arithmétique. - Le complément à deux a un seul zéro et permet au même circuit additif de faire la soustraction, c'est pourquoi il a gagné.
One's complement is preferred to two's complement because it has only one representation of zero. · Le complément à un est préféré au complément à deux car il n'a qu'une seule représentation du zéro.
The opposite: one's complement has two zeros, +0 and −0. Two's complement has one, and lets the adder do subtraction. · Le contraire : le complément à un a deux zéros, +0 et −0. Le complément à deux en a un, et permet au additionneur d'effectuer des soustractions.
Binary Coded Decimal
- In Binary Coded Decimal 二进制编码十进制 (BCD) each denary digit is stored as its own 4-bit pattern, using only
0000to1001. - 93 in BCD is
1001 0011, which is not the same as 93 in pure binary,0101 1101. Reading one as the other is a favourite exam trap. - Uses: calculators, digital clocks and seven-segment displays, where each digit is driven separately, and currency, where BCD avoids the rounding errors of storing $0.1$ in pure binary. The cost is wasted patterns, since
1010to1111are never used.
One digit, one nibble, one display
Décimal codé en binaire
- Dans le Décimal codé en binaire 二进制编码十进制 (BCD), chaque chiffre dénaire est stocké sous sa propre forme binaire sur 4 bits, utilisant uniquement
0000à1001. - 93 en BCD est
1001 0011, ce qui n'est pas la même chose que 93 en binaire pur,0101 1101. Lire l'un comme l'autre est un piège d'examen favori. - Usages : calculateurs, horloges numériques et afficheurs à sept segments, où chaque chiffre est piloté séparément, et monnaie, où le BCD évite les erreurs d'arrondi en stockant $0.1$ en binaire pur. Le coût est des motifs gaspillés, puisque
1010à1111ne sont jamais utilisés.
Un chiffre, un demi-octet, un affichage
Write the denary digit $9$ as a 4-bit BCD pattern. · Écrivez le chiffre décimal $9$ sous forme de motif BCD sur 4 bits.
$9$ is 1001. In BCD each denary digit gets its own nibble (0000–1001). · $9$ est 1001. En BCD, chaque chiffre décimal obtient sa propre demi-octet (0000–1001).
Match each bit pattern to what it represents. · Reliez chaque motif binaire à ce qu'il représente.
Nothing in the bits says how to read them. The agreed representation decides the value. · Rien dans les bits ne dit comment les lire. La représentation convenue détermine la valeur.
Marks that slip away
- Explain overflow with the register width the question gave, not with "it was more than 255".
- To negate, invert and add 1. Setting the top bit to 1 is sign and magnitude, a different scheme.
- Two's complement subtraction ends by discarding the final carry-out. Keeping it gives a nine-bit answer.
- BCD stores each digit separately; pure binary stores the whole number.
1001 0011is 93 in BCD and 147 in binary.
Pièges qui font perdre des points
- Expliquez le débordement avec la largeur du registre donnée dans l'énoncé, pas avec « c'était supérieur à 255 ».
- Pour négatif, inversez et ajoutez 1. Mettre le bit de tête à 1 est signe et magnitude, un schéma différent.
- La soustraction en complément à deux se termine par l'abandon du report final. Le conserver donne une réponse à neuf bits.
- Le BCD stocke chaque chiffre séparément ; le binaire pur stocke le nombre entier.
1001 0011est 93 en BCD et 147 en binaire.
You've got it
- add column by column with carries; overflow is a result needing more bits than the register holds, and the answer names that width
- subtract by adding the two's complement, invert and add 1, then discard the final carry
- signed: the MSB is the sign bit and carries $-2^{n-1}$; range $-2^{n-1}$ to $+2^{n-1}-1$; read a negative by inverting, adding 1 and negating
- one's complement inverts only and has two zeros; BCD stores each denary digit in its own nibble, for clocks, calculators and currency
Vous avez compris
- additionnez colonne par colonne avec les reports ; le débordement est un résultat nécessitant plus de bits que le registre ne contient, et la réponse nomme cette largeur
- soustrayez en ajoutant le complément à deux, inversez et ajoutez 1, puis jetez le report final
- signé : le MSB est le bit de signe et porte $-2^{n-1}$ ; étendue $-2^{n-1}$ à $+2^{n-1}-1$ ; lisez un négatif en inversant, ajoutant 1 et négatif
- complément à un n'inverse que et a deux zéros ; BCD stocke chaque chiffre dénaire dans son propre demi-octet, pour les horloges, calculateurs et monnaie