Binary arithmetic and signed integers · Aritmética binaria e enteros con signo
| English | Español |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | desbordamiento |
| two's complement/tuːz ˈkɒmplɪmənt/ | complemento a dos |
| register/ˈredʒɪstə/ | registro |
| sign bit/saɪn bɪt/ | bit de signo |
| most significant bit/məʊst sɪɡˈnɪfɪkənt bɪt/ | bit más significativo |
| one's complement/wʌnz ˈkɒmplɪmənt/ | complemento a uno |
| Binary Coded Decimal/ˈbaɪnəri ˈkəʊdɪd ˈdesɪml/ | Decimal codificado en binario |
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.
El banco que perdió un día
- El 1 de septiembre de 1983, el índice de la Bolsa de Valores de Vancouver se situaba en 524.811. Había abierto a 1000 veintidós meses antes y el mercado había subido todo ese tiempo.
- El programa recalculaba el índice después de cada operación, truncando en lugar de redondear cada vez. Cada truncamiento perdía una fracción de punto. Tres mil operaciones al día hicieron el resto.
- Cuando se recalculó correctamente, el índice era 1098.892: fue la aritmética, no el mercado, lo que lo redujo a la mitad.
- La aritmética sobre un número fijo de bits no es la aritmética que aprendiste en la escuela. Esta lección trata sobre la suma binaria, overflow (desbordamiento), resta por complemento a dos, enteros con signo y 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
Suma binaria
- Suma columna por columna desde la derecha, llevando a la siguiente columna, exactamente como en decimal.
- Las reglas: $0 + 0 = 0$; $0 + 1 = 1$; $1 + 1 = 10$, escribe 0 y lleva 1; $1 + 1 + 1 = 11$, escribe 1 y lleva 1.
0101$+$0011$=$1000, es decir, $5 + 3 = 8$.
Mismo método que en decimal, solo dos dígitos para llevar entre columnas
Binary & signed integers · Binario y enteros con signo
byte = Σ place values · byte = Σ valores de posición
See how an 8-bit pattern maps to a number (and how it would overflow past 255). · Ver cómo un patrón de 8 bits se mapea a un número (y cómo desbordaría más allá de 255).
Add the binary numbers 0101 + 0011. Give the 4-bit result. · Sume los números binarios 0101 + 0011. Dé el resultado de 4 bits.
$5 + 3 = 8$, which is 1000 in binary. · $5 + 3 = 8$, que es 1000 en binario.
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.
Desbordamiento (Overflow)
- El desbordamiento (overflow) ocurre cuando el resultado de un cálculo necesita más bits de los que puede contener el registro. La salida del acarreo de la columna más significativa se pierde, por lo que la respuesta almacenada es incorrecta.
- Es una propiedad del ancho del registro, no del número 255: en un registro de 16 bits, la misma suma es correcta.
- En la aritmética con signo, la señal reveladora es un bit de signo que cambia erróneamente: dos positivos que dan negativo, o dos negativos que dan positivo.
Overflow in binary addition means: · El desbordamiento en la suma binaria significa:
Overflow occurs when the sum is too large to fit in the available bits; the carry out of the leftmost column is lost. · El desbordamiento ocurre cuando la suma es demasiado grande para caber en los bits disponibles; el acarreo fuera de la columna más a la izquierda se pierde.
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.
Ejemplo resuelto: nombra el desbordamiento correctamente
- Suma los enteros sin signo de 8 bits
10110101y01101100y comenta el resultado. - La suma es
1 0010 0001, que necesita 9 bits. El resultado verdadero es 289. - Respuesta completa: ha ocurrido un desbordamiento, porque 289 es mayor que el valor máximo que puede contener un registro de 8 bits, que es 255; la salida del acarreo del bit más significativo se pierde, por lo que el resultado almacenado
0010 0001es 33, lo cual es incorrecto. - La puntuación consiste en nombrar el ancho del registro y decir que el resultado no puede representarse en él. Decir "la respuesta fue mayor que 255" solo no otorga puntos.
Two 8-bit unsigned integers are added and the result needs 9 bits. Which is the full-mark explanation? · Se suman dos enteros sin signo de 8 bits y el resultado necesita 9 bits. ¿Cuál es la explicación con puntuación completa?
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. · Nombre el ancho del registro, diga que el resultado no puede representarse en él y diga qué sucede con el acarreo. Las otras opciones mencionan un síntoma sin la causa.
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
Resta por complemento a dos
- Para calcular $A - B$: forma el complemento a dos de $B$ invirtiendo todos los bits y sumando 1, súmalo a $A$, luego descarta cualquier acarreo final de salida.
- $100 - 30$ en 8 bits: el complemento a dos de
0001 1110es1110 0001invertido, más 1, así que1110 0010. 0110 0100$+$1110 0010$=$1 0100 0110; descarta el 1 inicial y lee0100 0110$= 70$. ✓
La resta se convierte en suma, por eso los procesadores no necesitan restadores
What is the 4-bit two's complement of 0011? (invert, then add 1) · ¿Cuál es el complemento a dos de 4 bits de 0011? (invertir, luego sumar 1)
Invert 0011 → 1100, then add 1 → 1101 (which represents $-3$). · Invertir 0011 → 1100, luego sumar 1 → 1101 (que representa $-3$).
Put the steps of subtracting B from A by two's complement in order. · Ponga los pasos para restar B de A mediante complemento a dos en orden.
Invert, add one, add, discard. The discard is what keeps the answer in the register's width. · Invertir, sumar uno, sumar, descartar. El descarte es lo que mantiene la respuesta dentro del ancho del registro.
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
Enteros con signo en complemento a dos
- En un número en complemento a dos de $n$ bits, el bit más significativo es el bit de signo: 0 significa positivo, 1 significa negativo. Alternativamente, el bit superior tiene un valor posicional negativo, $-2^{n-1}$.
- Para leer un número negativo: invierte todos los bits, suma 1 y coloca un signo menos delante.
1011 0100se invierte a0100 1011, más 1 es0100 1100$= 76$, por lo que el valor es $-76$. Verifica con el valor posicional: $-128 + 32 + 16 + 4 = -76$. ✓ - Para $n$ bits, el rango es $-2^{n-1}$ a $+2^{n-1} - 1$: 8 bits dan $-128$ a $+127$, 12 bits dan $-2048$ a $+2047$. El valor más negativo es un 1 seguido de ceros; el más positivo es un 0 seguido de unos.
11111111 es 255 leído de una manera y −1 de la otra
Two's complement signed bits · Bits con signo en complemento a dos
The leftmost bit carries a negative · negativa place value. Flip any bit — or hit Negate (invert every bit, then add 1) — and watch the signed value change. · El bit más a la izquierda tiene un valor de posición negativo. Invierta cualquier bit o haga clic en Negar (invertir todos los bits, luego sumar 1) y observe cómo cambia el valor con signo.
Read the 8-bit two's complement number 11111101 as a signed denary value. · Lea el número complementado a dos de 8 bits 11111101 como un valor decimal con signo.
MSB is 1 (negative). Invert → 00000010, add 1 → 00000011 $= 3$, so the value is $-3$. · El bit más a la izquierda (MSB) es 1 (negativo). Invertir → 00000010, sumar 1 → 00000011 $= 3$, por lo tanto el valor es $-3$.
What is the largest positive value an 8-bit two's complement number can hold? · ¿Cuál es el valor positivo más grande que puede contener un número complementado a dos de 8 bits?
Range is $-2^{7}$ to · hasta $2^{7}-1$, i.e. $-128$ to · hasta $+127$. The maximum is 01111111 = 127. · El rango es $-2^{7}$ a $2^{7}-1$, es decir, $-128$ a $+127$. El máximo es 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.
Ejemplo resuelto: escribe −108 en 12 bits
- Comienza con $+108$ en 12 bits: $108 = 64 + 32 + 8 + 4$, así que
0000 0110 1100. - Invierte todos los bits:
1111 1001 0011. Suma 1:1111 1001 0100. - Verifica con valores posicionales, donde el bit superior vale $-2048$: $-2048 + 1024 + 512 + 256 + 128 + 16 + 4 = -108$. ✓
- El error más común es signo y magnitud: establecer el bit superior en 1 y dejar el resto. Ese es un esquema diferente, más antiguo y no obtiene puntos aquí.
Write −108 as a 12-bit two's complement number (spaces allowed). · Escriba −108 como un número complementado a dos de 12 bits (se permiten espacios).
+108 is 0000 0110 1100; invert to 1111 1001 0011 and add 1. Check: −2048 + 1024 + 512 + 256 + 128 + 16 + 4 = −108. · +108 es 0000 0110 1100; invertir a 1111 1001 0011 y sumar 1. Verificación: −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.
Complemento a uno
- El complemento a uno es el esquema más antiguo: un negativo se crea invirtiendo todos los bits del positivo, sin paso de sumar 1. $+30$ es
0001 1110, así que $-30$ es1110 0001. - Su inconveniente es tener dos ceros,
0000 0000y1111 1111, lo que desperdicia un patrón de bits y complica la aritmética. - El complemento a dos tiene un solo cero y permite que el mismo circuito sumador realice la resta, por lo que ganó.
One's complement is preferred to two's complement because it has only one representation of zero. · El complemento a unos es preferible al complemento a dos porque solo tiene una representación del cero.
The opposite: one's complement has two zeros, +0 and −0. Two's complement has one, and lets the adder do subtraction. · Lo contrario: el complemento a unos tiene dos ceros, +0 y −0. El complemento a dos tiene uno, y permite al sumador hacer resta.
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
Decimal codificado en binario (BCD)
- En Decimal codificado en binario (BCD), cada dígito decimal se almacena como su propio patrón de 4 bits, usando solo
0000a1001. - 93 en BCD es
1001 0011, lo cual no es lo mismo que 93 en binario puro,0101 1101. Leer uno como el otro es una trampa favorita en exámenes. - Usos: calculadoras, relojes digitales y pantallas de siete segmentos, donde cada dígito se controla por separado, y moneda, donde el BCD evita errores de redondeo al almacenar $0.1$ en binario puro. El costo son patrones desperdiciados, ya que
1010a1111nunca se usan.
Un dígito, un nibble, una pantalla
Write the denary digit $9$ as a 4-bit BCD pattern. · Escriba el dígito decimal $9$ como un patrón BCD de 4 bits.
$9$ is 1001. In BCD each denary digit gets its own nibble (0000–1001). · $9$ es 1001. En BCD, cada dígito decimal recibe su propia nibble (0000–1001).
Match each bit pattern to what it represents. · Empareje cada patrón de bits con lo que representa.
Nothing in the bits says how to read them. The agreed representation decides the value. · Nada en los bits dice cómo leerlos. La representación acordada decide el valor.
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.
Puntos que se escapan
- Explica el desbordamiento con el ancho del registro que dio la pregunta, no con "fue mayor que 255".
- Para negar, invierte y suma 1. Establecer el bit superior en 1 es signo y magnitud, un esquema diferente.
- La resta por complemento a dos termina descartando el acarreo final de salida. Mantenerlo da una respuesta de nueve bits.
- El BCD almacena cada dígito por separado; el binario puro almacena el número completo.
1001 0011es 93 en BCD y 147 en binario.
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
Lo has logrado
- suma columna por columna con los acarreos; el desbordamiento es un resultado que necesita más bits de los que contiene el registro, y la respuesta nombra ese ancho
- resta sumando el complemento a dos, invierte y suma 1, luego descarta el acarreo final
- con signo: el bit MSB es el bit de signo y tiene $-2^{n-1}$; rango $-2^{n-1}$ a $+2^{n-1}-1$; lee un negativo invirtiendo, sumando 1 y negándolo
- el complemento a uno solo invierte y tiene dos ceros; el BCD almacena cada dígito decimal en su propio nibble, para relojes, calculadoras y moneda