Binary arithmetic and signed integers · Aritmética binária e inteiros sinalizados
| English | Português |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | overflow |
| two's complement/tuːz ˈkɒmplɪmənt/ | complemento de dois |
| register/ˈredʒɪstə/ | registrador |
| sign bit/saɪn bɪt/ | bit de sinal |
| most significant bit/məʊst sɪɡˈnɪfɪkənt bɪt/ | bit mais significativo |
| one's complement/wʌnz ˈkɒmplɪmənt/ | complemento de um |
| Binary Coded Decimal/ˈbaɪnəri ˈkəʊdɪd ˈdesɪml/ | Decimal Codificado em Binário |
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.
O banco que perdeu um dia
- Em 1º de setembro de 1983 o índice da Bolsa de Valores de Vancouver estava em 524.811. Ele havia aberto em 1000 vinte e dois meses antes, e o mercado tinha subido o tempo todo.
- O programa recalculava o índice após cada negociação, truncando em vez de arredondar cada vez. Cada truncamento perdia uma fração de ponto. Três mil negociações por dia faziam o resto.
- Quando foi recomputado corretamente o índice era 1098.892: a aritmética, não o mercado, tinha reduzido pela metade.
- Aritmética com número fixo de bits não é a aritmética que você aprendeu na escola. Esta lição é adição binária, overflow overflow, subtração por complemento de dois complemento de dois, inteiros com sinal e 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
Adição binária
- Some coluna por coluna da direita, carregando para a próxima coluna, exatamente como no denary.
- As regras: $0 + 0 = 0$; $0 + 1 = 1$; $1 + 1 = 10$, escreva 0 e carregue 1; $1 + 1 + 1 = 11$, escreva 1 e carregue 1.
0101$+$0011$=$1000, isso é $5 + 3 = 8$.
Mesmo método que denary, apenas dois dígitos para carregar entre
Binary & signed integers · Binário & inteiros sinalizados
byte = Σ place values · byte = Σ valores de posição
See how an 8-bit pattern maps to a number (and how it would overflow past 255). · Veja como um padrão de 8 bits mapeia para um número (e como transbordaria além de 255).
Add the binary numbers 0101 + 0011. Give the 4-bit result. · Some os números binários 0101 + 0011. Dê o resultado de 4 bits.
$5 + 3 = 8$, which is 1000 in binary. · $5 + 3 = 8$, que é 1000 em binário.
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.
Overflow
- Overflow acontece quando o resultado de um cálculo precisa de mais bits do que o registro registro pode segurar. O carry para fora da coluna mais significativa é perdido, então a resposta armazenada está errada.
- É uma propriedade da largura do registro, não do número 255: em um registro de 16 bits a mesma soma está bem.
- Na aritmética com sinal, o indicador é um bit de sinal que inverte errado: dois positivos dando negativo, ou dois negativos dando positivo.
Overflow in binary addition means: · Estouro na adição binária significa:
Overflow occurs when the sum is too large to fit in the available bits; the carry out of the leftmost column is lost. · O estouro ocorre quando a soma é grande demais para caber nos bits disponíveis; o carry (transporte) da coluna mais à esquerda é perdido.
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.
Exemplo resolvido: nomeie o overflow adequadamente
- Some os inteiros sem sinal de 8 bits
10110101e01101100e comente sobre o resultado. - A soma é
1 0010 0001, que precisa de 9 bits. O resultado verdadeiro é 289. - Resposta completa: ocorreu overflow, porque 289 é maior que o maior valor que um registro de 8 bits pode segurar, 255; o carry para fora do bit mais significativo é perdido, então o resultado armazenado
0010 0001é 33, o que está errado. - A marca é por nomear a largura do registro e dizer que o resultado não pode ser representado nele. "A resposta foi mais que 255" sozinho não pontua.
Two 8-bit unsigned integers are added and the result needs 9 bits. Which is the full-mark explanation? · Dois inteiros sem sinal de 8 bits são somados e o resultado precisa de 9 bits. Qual é a explicação completa com nota máxima?
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. · Nomeie a largura do registro, diga que o resultado não pode ser representado nela e diga o que acontece com o carry. As outras opções afirmam um sintoma sem a 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
Subtração por complemento de dois
- Para calcular $A - B$: forme o complemento de dois de $B$ invertendo todos os bits e somando 1, some com $A$, depois descarte qualquer carry final.
- $100 - 30$ em 8 bits: complemento de dois de
0001 1110é1110 0001invertido, mais 1, então1110 0010. 0110 0100$+$1110 0010$=$1 0100 0110; descarte o 1 inicial e leia0100 0110$= 70$. ✓
Subtração torna-se adição, que é por que processadores não precisam de subtrator
What is the 4-bit two's complement of 0011? (invert, then add 1) · Qual é o complemento de dois de 4 bits de 0011? (inverter, depois adicionar 1)
Invert 0011 → 1100, then add 1 → 1101 (which represents $-3$). · Inverta 0011 → 1100, depois adicione 1 → 1101 (que representa $-3$).
Put the steps of subtracting B from A by two's complement in order. · Coloque as etapas de subtrair B de A pelo complemento de dois em ordem.
Invert, add one, add, discard. The discard is what keeps the answer in the register's width. · Inverta, adicione um, adicione, descarte. O descarte é o que mantém a resposta na largura do 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
Inteiros com sinal por complemento de dois
- Em um número de complemento de dois de $n$ bits, o bit mais significativo bit mais significativo é o bit de sinal bit de sinal: 0 significa positivo, 1 significa negativo. Alternativamente, o bit superior carrega um valor negativo posicional, $-2^{n-1}$.
- Para ler um número negativo: inverta todos os bits, adicione 1, depois coloque um sinal de menos na frente.
1011 0100inverte para0100 1011, mais 1 é0100 1100$= 76$, então o valor é $-76$. Verifique por valor posicional: $-128 + 32 + 16 + 4 = -76$. ✓ - Para $n$ bits, a faixa é de $-2^{n-1}$ a $+2^{n-1} - 1$: 8 bits dão de $-128$ a $+127$, 12 bits dão de $-2048$ a $+2047$. O valor mais negativo é um 1 seguido de zeros; o mais positivo é um 0 seguido de uns.
11111111 é 255 lido de uma forma e −1 lido da outra
Two's complement signed bits · Bits sinalizados em complemento de dois
The leftmost bit carries a negative · negativo place value. Flip any bit — or hit Negate (invert every bit, then add 1) — and watch the signed value change. · O bit mais à esquerda carrega um valor de posição negativo. Alterne qualquer bit — ou clique em Negate (inverta todos os bits, depois adicione 1) — e veja o valor sinalizado mudar.
Read the 8-bit two's complement number 11111101 as a signed denary value. · Leia o número de complemento de dois de 8 bits 11111101 como um valor decimal com sinal.
MSB is 1 (negative). Invert → 00000010, add 1 → 00000011 $= 3$, so the value is $-3$. · MSB é 1 (negativo). Inverta → 00000010, adicione 1 → 00000011 $= 3$, então o valor é $-3$.
What is the largest positive value an 8-bit two's complement number can hold? · Qual é o maior valor positivo que um número de complemento de dois de 8 bits pode armazenar?
Range is $-2^{7}$ to · até $2^{7}-1$, i.e. $-128$ to · até $+127$. The maximum is 01111111 = 127. · Faixa é $-2^{7}$ a $2^{7}-1$, ou seja, $-128$ a $+127$. O máximo é 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.
Exemplo resolvido: escreva −108 em 12 bits
- Comece de $+108$ em 12 bits: $108 = 64 + 32 + 8 + 4$, então
0000 0110 1100. - Inverta todos os bits:
1111 1001 0011. Adicione 1:1111 1001 0100. - Verifique com valores posicionais, onde o bit superior vale $-2048$: $-2048 + 1024 + 512 + 256 + 128 + 16 + 4 = -108$. ✓
- O erro mais comum é sinal e magnitude: definir o bit superior como 1 e deixar o resto. Isso é um esquema diferente, mais antigo e pontua zero aqui.
Write −108 as a 12-bit two's complement number (spaces allowed). · Escreva −108 como um número de complemento de dois de 12 bits (espaços permitidos).
+108 is 0000 0110 1100; invert to 1111 1001 0011 and add 1. Check: −2048 + 1024 + 512 + 256 + 128 + 16 + 4 = −108. · +108 é 0000 0110 1100; inverte-se para 1111 1001 0011 e adiciona-se 1. Verifique: −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 de uns
- Complemento de uns complemento de uns é o esquema mais antigo: um negativo é feito invertendo todos os bits do positivo, sem passo de adicionar 1. $+30$ é
0001 1110, então $-30$ é1110 0001. - Sua desvantagem é dois zeros,
0000 0000e1111 1111, o que desperdiça um padrão de bits e complica a aritmética. - Complemento de dois tem um zero e permite que o mesmo circuito de adição faça subtração, que é por que venceu.
One's complement is preferred to two's complement because it has only one representation of zero. · O complemento de um é preferível ao complemento de dois porque ele tem apenas uma representação de zero.
The opposite: one's complement has two zeros, +0 and −0. Two's complement has one, and lets the adder do subtraction. · O oposto: o complemento de um tem dois zeros, +0 e −0. O complemento de dois tem um, e permite que o somador faça subtração.
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 Codigoado Binário
- No Decimal Codigoado Binário decimal codificado binário (BCD) cada dígito denary é armazenado como seu próprio padrão de 4 bits, usando apenas
0000a1001. - 93 em BCD é
1001 0011, que não é o mesmo que 93 em binário puro,0101 1101. Ler um como o outro é uma armadilha favorita de exame. - Usos: calculadoras, relógios digitais e pantallas de sete segmentos, onde cada dígito é acionado separadamente, e moeda, onde BCD evita erros de arredondamento ao armazenar $0.1$ em binário puro. O custo é padrões desperdiçados, já que
1010a1111nunca são usados.
Um dígito, um nibble, uma pantalla
Write the denary digit $9$ as a 4-bit BCD pattern. · Escreva o dígito decimal $9$ como um padrão BCD de 4 bits.
$9$ is 1001. In BCD each denary digit gets its own nibble (0000–1001). · $9$ é 1001. No BCD, cada dígito decimal recebe seu próprio nibble (0000–1001).
Match each bit pattern to what it represents. · Combine cada padrão de bits com o que ele representa.
Nothing in the bits says how to read them. The agreed representation decides the value. · Nada nos bits diz como lê-los. A representação acordada decide o 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.
Marcas que escapam
- Explique overflow com a largura do registro que a questão deu, não com "foi mais que 255".
- Para negar, inverte e adiciona 1. Definir o bit superior como 1 é sinal e magnitude, um esquema diferente.
- Subtração por complemento de dois termina descartando o carry final. Mantê-lo dá uma resposta de nove bits.
- BCD armazena cada dígito separadamente; binário puro armazena o número inteiro.
1001 0011é 93 em BCD e 147 em binário.
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
Entendeu?
- some coluna por coluna com carries; overflow é um resultado precisando de mais bits do que o registro segura, e a resposta nomeia essa largura
- subtraia somando o complemento de dois, inverta e adicione 1, depois descarte o carry final
- com sinal: o MSB é o bit de sinal e carrega $-2^{n-1}$; intervalo $-2^{n-1}$ a $+2^{n-1}-1$; leia um negativo invertendo, adicionando 1 e negando
- complemento de uns inverte apenas e tem dois zeros; BCD armazena cada dígito denary em seu próprio nibble, para relógios, calculadoras e moeda