Uma explicação (não tão simples) do que significa "complemento 2"

[fredericopissarra]

Em linguagens com tipagem, como é o caso de C, existem inteiros sinalizados (possuem valores negativos) e não sinalizados (apenas valores positivos). É intuitivo, para o estudante, pensar que valores negativos como sendo aqueles que tem um sinal '-' na frente do número, no entanto, não é assim que as coisas são feitas pelo processador. Não há como colocar um '-' na frente de um valores binários, nos circuitos do processador ou do computador.

Acredito que eu já tenha digo, por aqui ou em meu blog, que valores inteiros sinalizados são meras representações e que, na realidade, eles não tenham sinal algum. Ou seja, a maneira como são interpretados é que dá sinal ao valor, na hora de ser convertido de e para a base decimal... É também comum que essa representaçao use a técnica do "complemento 2", onde o bit mais significativo do valor indica ao programa que esse valor pode ser interpretado como sendo negativo. Mas, o que diabos significa "complemento 2"? Que "complemento" é esse?

Daqui por diante farei de conta que nosso processador hipotético tenha registradores de apenas 4 bits só para não ficar escrevendo um montão de bits, mas os raciocínios aplicam-se a 8, 16, 32, 64 e a 128 bits facilmente.

Comecemos com os inteiros não sinalizados... Com 4 bits, todos os valores possíveis são de 0b0000 até 0b1111, ou, em decimal, de 0 a 15. Não há qualquer mistério ai. As operações aritméticas funcionam perfeitamente bem, desde que não tenhamos condições de overflow (exemplo: 0b0000 - 0b0001 = 0b1111, ou 0 - 1  = 15?). Se quisermos trabalhar com esses valores como se existissem valores negativos, um macete é encarar o bit mais significativo (msb) como se fosse um indicador de sinal (como se fosse o '-'). Se o msb for 0 temos um valor positivo, na faixa de 0 a 7 (0b0000 até 0b0111), se o msb for 1, temos valores negativos (discussão sobre a faixa segue abaixo).

Poderíamos simplesmente parar ai, ou seja, -1 poderia ser representado como 0b1_001 (msb='-' e 1), mas isso causa problemas nas operações aritméticas fundamentais... Como vimos, 0b0000 - 0b0001 = 0b1111, ou seja, nessa representação teríamos como resposta -7 (que poderia ser encarada como uma condição de overflow, mas não é, como veremos).

Outra técnica é a inversão de todos os bits de um valor positivo para obter o negativo e usarmos apenas o bit 1 como sinalização. Com o mesmo exemplo, -1 seria ~0b0001 = 0b1110, ou seja, o "inverso" de 1 (operação NOT) seria -6, o que ainda está errado. Mas essa representação é usada em computadores antigos, com alguns ajustes. Por exemplo, sempre que toparmos com o msb=1 devemos inverter o valor para obter seu absoluto... assim, ~0b1110 volta a ser 1, interpretado como negativo, e estaria tudo certo. Mas temos um problema: E quanto ao valor 0b1111? Seu inverso, obviamente, é 0b0000, o que significaria que temos +0 e -0 e, usando aritmética binária elementar 0b0000 - 0b0001 = 0b1111, ou seja, nessa representação temos +0 - +1 = -0 (menos zero?).

A solução para isso foi o uso do conceito de complementação da faixa dos positivos. Se temos 8 valores positivos de 0b0000 até 0b0111, na sequência ascendente, podemos copiar a sequência, mudando apenas o msb para 1 e colocando-a "antes" da faixa dos positivos (de 0b1000 até 0b1111). Assim:

0b1000, 0b1001, 0b1010, ..., 0b000, 0b0001, ...

Assim, temos 8 valores negativos antes do zero, na sequência {-8, -7, -6, ... 0, +1, ..., 7}. Ou, de outra maneira, um valor sinalizado pode ser calculado de acordo com a seguinte equação:

Eis o "complemento 2", trata-se apenas da "complementação" da faixa dos inteiros positivos (quando s=0), na sequência, ascendente que mostrei, pela mesma sequência, mas com s=1. Onde: s é o msb e P é a precisão, em bits, do valor (lembrando que "precisão" é a quantidade de bits que expressa o valor absoluto - isso vale tanto para inteiros quanto para ponto flutuante). No nosso caso, P=3 e s é o bit 3. Vejamos como fica -1: Se 0b1111 é -1, então, pela equação acima temos (-1*2³)+(4+2+1) = -8+7 = -1. Isso faz com que as operações aritméticas fiquem corretas, exceto no caso de overflows, e não temos mais dois zeros: 0b1000 = -8.

Existe, é claro, uma aparente assimetria de valores. No lado negativo o menor valor é -8 e no lado positivo o maior é +7. Isso é inevitável, já que temos uma quantidade par de valores possíveis, dividindo toda a faixa em dois blocos de 8 valores, onde um deles é 0 (que ficará do lado positivo). O único problema aqui é que -8 será sempre -8, se interpretado com sinal.

Não é difíil perceber, embora eu gastaria muitas palavras aqui para descrever, que a fórmula acima pode ser substituída, lógicamente, por uma simples operação NOT seguida de um incremento de uma unidade para realizar a transformação de um valor positivo para negativo e vice-versa, ou seja, a operação de negação (o '-' unário de C e a instrução NEG do x86) só fazem y=~x+1. E essa é outra interpretação do significado do "complemento 2": Se o "complemento 1" for definido como a simples inversão, ao somar 1 temos um "complemento 2".

Quanto aos overflows, eles acontecem, como sempre, na passagem dos extremos da faixa. -8 - 1 resultará em +7, assim como 7+1 resultatá em -8.

Resumindo: inteiros sinalizados são uma representação, o seu processador sempre lida com valores sem sinal, mas mantém flags interpretando os valores com e sem sinal (CF para não sinalizados e SF e OF para sinalizados - e ZF para ambos -- em outros processadores, como ARM, por exemplo, os flags são nomeados, respectivamente, C, N, V e Z, de carry, "negativo", "oVerflow" e Zero).

Agora dá para entender porque, em C, ao fazer,:

unsigned int x = -1;

Obtemos 0xffffffff?