Inteiros, sinal e overflow

O código 1011 vale 11 sem sinal e -5 em complemento para dois com quatro bits. Os bits mantêm-se; a interpretação muda os pesos. Antes de calcular, precisamos de conhecer a base, a representação e a largura.

Pesos posicionais

Na base $b$, cada algarismo $d_i$ está entre 0 e $b-1$ e tem peso $b^i$; a vírgula separa os pesos inteiros dos fracionários, com

$$x=\sum_i d_i b^i.$$

Por exemplo, $10110{,}101_2$ soma os pesos $16+4+2+1/2+1/8$:

$$10110{,}101_2=16+4+2+\frac12+\frac18=22{,}625_{10}.$$

O índice $i=0$ marca o algarismo das unidades, à esquerda da vírgula, enquanto $-1,-2,\ldots$ marcam a parte fracionária; o subscrito 2 ou 10 indica a base e não faz parte do número.

O bit mais significativo, MSB, é o de maior peso; o LSB é o de menor peso da palavra. Um byte tem 8 bits. KiB significa $2^{10}$ bytes; kB significa $10^3$ bytes. Indica a unidade quando calculares capacidade.

Converter a parte inteira

Para converter 173 para binário, divide sucessivamente por 2 e guarda os restos. Cada linha mostra um quociente com o resto correspondente:

Divisão	Quociente	Resto
173 / 2	86	1
86 / 2	43	0
43 / 2	21	1
21 / 2	10	1
10 / 2	5	0
5 / 2	2	1
2 / 2	1	0
1 / 2	0	1

Lê os restos de baixo para cima: $173=10101101_2$. O primeiro resto corresponde ao peso $2^0$, por isso não pode ficar à esquerda; confirma com $128+32+8+4+1=173$.

O método funciona para qualquer base inteira; para hexadecimal, $173=10\times16+13$, pelo que obtemos AD, usando A para 10 e D para 13.

Converter a parte fracionária

Multiplica a fração por 2; a parte inteira obtida é o próximo bit e continua-se com a parte fracionária, como em

$$0{,}625\times2=1{,}25,\quad0{,}25\times2=0{,}5,\quad0{,}5\times2=1.$$

Os bits lêem-se agora por ordem direta e são 101, logo $173{,}625=10101101{,}101_2$; para uma base $b$, substitui a multiplicação por 2 por uma multiplicação por $b$.

Uma fração reduzida tem expansão binária finita se o denominador for uma potência de 2. Por exemplo, $3/8$ termina; $1/10$ não termina porque o denominador contém um fator 5. Se parares após $n$ bits, truncaste a representação, e o valor guardado pode diferir do pretendido.

Agrupar bits

Como $16=2^4$, cada algarismo hexadecimal corresponde a 4 bits, e como $8=2^3$, cada algarismo octal corresponde a 3 bits. Agrupa a partir da vírgula para fora e acrescenta zeros apenas nas extremidades necessárias:

$$10101101{,}101_2=1010\ 1101{,}1010_2=\mathrm{AD}{,}\mathrm A_{16}.$$

Em octal, $010\ 101\ 101{,}101_2=255{,}5_8$. O zero acrescentado à esquerda não altera o inteiro, tal como o zero acrescentado à direita da fração não altera o seu valor.

Quantos bits são necessários

Com $n$ bits há $2^n$ códigos; o símbolo $\lceil x\rceil$ significa o menor inteiro maior ou igual a $x$. Para distinguir $M$ situações precisamos de $\lceil\log_2M\rceil$ bits, por isso números de 0 até 300, com 301 valores, exigem 9 bits, pois 8 bits só dão 256 códigos.

Um hexadecimal de 32 bits tem 8 algarismos, porque $32/4=8$. Não confundas o número de algarismos impressos com o número de bits: 0x0000000F ocupa 32 bits nesta escrita, mas o valor 15 cabe em 4 bits sem sinal.

Três representações

Uma palavra de $n$ bits tem $2^n$ padrões. O hardware pode somar esses padrões sem saber se os interpretamos com ou sem sinal. A interpretação determina o intervalo válido e a condição de overflow.

Representação em $n$ bits	Intervalo	Zeros
Sem sinal	$0$ a $2^n-1$	Um
Sinal e magnitude	$-(2^{n-1}-1)$ a $2^{n-1}-1$	Dois
Complemento para dois	$-2^{n-1}$ a $2^{n-1}-1$	Um

Em sinal e magnitude, o MSB indica o sinal e os restantes bits dão o módulo. Em 8 bits, 10010110 representa $-22$, mas 10000000 é um zero negativo. Somar diretamente os códigos não implementa a adição dos valores com sinal.

Em complemento para dois, o MSB tem peso negativo, com

$$x=-b_{n-1}2^{n-1}+\sum_{i=0}^{n-2}b_i2^i.$$

Assim 11101010 vale $-128+64+32+8+2=-22$, que também se lê como o inteiro sem sinal 234 menos 256.

Negação e extensão

Para representar $-22$ em 8 bits, escreve $22=00010110$, inverte (11101001) e soma 1 (11101010); isto calcula $2^8-22$.

O mínimo $-128$ não tem simétrico positivo em 8 bits, pois inverter e somar 1 ao código 10000000 devolve o mesmo padrão e não produz um $+128$ representável.

Ao aumentar a largura, números sem sinal recebem zeros à esquerda. Em complemento para dois, repete-se o bit de sinal: 11101010 passa a 11111111 11101010. Em sinal e magnitude, conserva-se o bit de sinal na nova posição e acrescentam-se zeros à magnitude. Não mistures estas regras.

Adição e subtração

A soma de palavras conserva os $n$ bits inferiores, ou seja, calcula módulo $2^n$. A subtração usa $A-B=A+(\overline B+1)$.

Segue $100+40$ em 8 bits. A soma matemática é 140, código 10001100. Sem sinal, o resultado está certo. Em C2, esse código vale $-116$: 140 excede o máximo 127.

Segue agora $-1+1$. Os códigos somam 11111111 + 00000001 = 1 00000000. Há carry para fora, mas a palavra guardada 00000000 vale 0, que é o resultado certo em C2.

O par carry/overflow distingue os mundos: usa o carry final para sem sinal e $V$ para C2. Os três casos seguintes mostram as combinações sem mudar a largura a meio da conta:

Soma em 4 bits	Soma completa dos códigos	Palavra guardada	Carry	Overflow C2
$7+1$	0 1000	1000, valor -8	0	Sim: 8 excede 7
$-1+1$	1 0000	0000, valor 0	1	Não
$-8+(-1)$	1 0111	0111, valor 7	1	Sim: -9 é menor que -8

O carry pertence à soma dos códigos sem sinal. Para C2, compara o resultado matemático com o intervalo ou aplica as regras de sinais. O somador é o mesmo nos dois casos; a pergunta que fazes aos bits é que muda. Por isso, o mesmo padrão pode ser válido sem sinal e inválido com sinal, ou o inverso: carry e overflow com sinal variam de forma independente, e as quatro combinações são possíveis. Escreve a largura e a interpretação antes de avaliar qualquer soma.

Operação	Overflow com sinal
$A+B$	Entradas com o mesmo sinal e resultado com sinal diferente
$A-B$	Entradas com sinais diferentes e resultado com sinal diferente de $A$

Num somador, o overflow com sinal também é $V=C_{n-1}\oplus C_n$: compara o carry que entra no bit de sinal com o que sai. Para adição sem sinal, $C_n=1$ indica overflow. Na subtração por complemento, um carry final 1 indica que não foi necessário empréstimo.

Segue $100-(-40)$ em 8 bits. A soma matemática é 140, que ultrapassa 127. O circuito soma 01100100 a 00101000 e guarda 10001100, lido como -116: os operandos tinham sinais diferentes e o resultado tem sinal diferente do primeiro. No outro sentido, $-100-40=-140$ guarda 01110100, lido como +116. A regra vale nos dois sentidos.

Multiplicação e comparação

O produto exato de dois números de $n$ bits pode precisar de $2n$ bits. Para $13\times11$, os produtos parciais binários são os deslocamentos de 1101 correspondentes aos bits 1 de 1011: $13+26+104=143$. Em 8 bits com sinal, 143 não cabe, embora caiba em 8 bits sem sinal.

Para multiplicar negativos sem perder o sinal, estende os operandos para a largura do resultado antes de construir os produtos, ou usa uma operação de multiplicação com sinal; conservar só os bits inferiores dá o mesmo padrão modular, mas perde a informação de que o produto completo não cabe.

Sem sinal, 11111111 é maior que 00000001. Com sinal, representa $-1$ e é menor que 1. A comparação deve usar a interpretação do problema; ordenar códigos como inteiros sem sinal não ordena os negativos corretamente.

Escolher a largura

Para representar todos os valores de $-90$ a 90, exige-se $2^{n-1}\ge90$ e $2^{n-1}-1\ge90$. Com 7 bits, o máximo é 63, e com 8 é 127, por isso a largura mínima é 8.

Não decidas a largura só pelo módulo do valor mínimo. O intervalo assimétrico permite representar $-128$ em 8 bits, mas não $+128$. Antes de uma conta, escreve o intervalo; depois compara o resultado matemático com esse intervalo.