Codificando bits em números negativos e positivos

Neste post irei demonstrar e explicar como funciona a codificação de números negativos e positivos.

Usarei o termo encoding ao invés de codificação por ser mais familiar para os devs.

Os exemplos estarão em Rust.

O que é Encoding

O que é encoding? Bem, encoding é o processo de mapear uma sequência de bits para um valor X.

Considere a seguinte sequência de bits:

0000

Aqui temos 4 bits. Todos os bits tem 0 como seu valor. Você já deve saber que, quando todos os bits são 0, ele normalmente representa o 0 em decimal.

Irei trabalhar com decimais por ser simples e direto. No entanto, a notação funciona para Octal e Hexadecimal também, caso reste dúvidas.

No entanto, o bit 0 pode ser o que eu quiser. Eu posso “encode” o bit 0 para a seguinte string: “The Elder Scrolls: Skyrim”. Eu posso mapear 00 para uma coisa complemente diferente, tal como valor numérico: 101.

Bits não significam nada sozinhos. O seu valor depende inteiramente do contexto. Isso significa que uma mesma sequência de bits pode representar infitas coisas dependendo do contexto. O que muda não são os bits, mas a interpretação deles. Iremos trabalhar com números nestes post.

Por debaixo dos panos, o mesmo ocorre quando escrevemos let x = 10. Como é de conhecimento comum, computadores usam base 2 (binária). Então como estamos vendo o número 10? Eu não só estou vendo o número 10, como é rotineiro manipular informação usando decimais ao invés de base binária!

Enconding Unsigned numbers

Para quem vêm do Python, JavaScript, e linguagens de alto nível, normalmente não se preocupam com multiplos tipos para valores numéricos, tais como u8, u16, u32, u64, u128 e outras variantes. Para que fique de fácil entendimento, um número unsigned é um valor pertencente ao conjunto dos números naturais. Ou seja, não é fracionário e nem pode ser negativo.

Eu não irei entrar em comprovação matemática. Eu irei demonstrar na prática com código de alto nível como funciona.

Considere a seguinte sequência de bits:

0 0 0 1 <- bit sequence3 2 1 0 <- bit index

Temos um bit de valor 1 e o restante com o valor de 0, totalizando 4 bits.

Dizemos que, quando um bit tem o valor de 1, ele contribui x times 2^i onde x é o valor do bit, e i é o posicionamento dele. Vamos fazer o processo passo a passo:

0 0 0 1 1 x 2^0 = 10 x 2^1 = 0 0 x 2^2 = 00 x 2^3 = 00 + 0 + 0 + 1 = 1 

Se você não entendeu o que aconteceu aqui, você provavelmente não sabe, ou não lembra como funciona potenciação e multiplicação por zero. Ensinar isto foge do escopo do post.

Perceba que no final, após calcular a contribuição de cada bit, somamos tudo e é retornado o valor decimal: 1. Isto significa que, 0001 é equivalente ao número 1. Portanto, ao escrever:

let x = 1;

Nós vemos um decimal, mas o computador trabalha com 0001.

Um detalhe importante. Eu usei 4 bits por questões de simplicidade. Normalmente trabalhamos com 8 bits em diante. A boa nóticia é que zero a esquerda não altera o valor, portanto:

0001 = 00000001

São equivalentes. Daqui em diante, continuarei usando 4 bits.

Um ponto interessante é que, podemos determinar o valor mínimo e máximo que uma sequência de bits pode representar da seguinte forma para unsigned numbers:

0 a 2^n onde n é o comprimento da sequência de bits. Neste caso é 4, portanto o valor máximo que eu posso expressar usando 4 bits é 2^4 = 15.

Antes que alguém corra para me corrigir, o valor é 15 porque o 0 esta incluso. Porém entendemos que na matemática seria 16.

Existe uma propriedade que garante os números nunca colidam. Isso significa que cada sequência de bit representa apenas uma única coisa, e que o processo de decimal para bits, e de bits para decimal sempre retorna o mesmo valor. Esta propriedade é matemática e foge do escopo do post.

Encoding signed numbers

Signed numbers representa números do conjunto de números inteiros. Portanto isto engloba números negativos, aumentando a complexidade da coisa.

Apesar de relativamente mais difícil de entender conceitualmente, a ideia é praticamente a mesma. A diferença reside no bit mais a esquerda.

1001

Para quem teve o trabalho de mapear sequências de bits do 0 até o 15, assim como eu, sabe que 1001 é o mesmo que 9 em decimal. No entanto, quando estamos lidando com números signed , não é 9, mas -7.

A cabeça pode está explodindo agora, mas calma, relaxa.

Antes de mais nada, é importante ressaltar que, estamos usando um algoritmo específico para este exemplo, o two’s complement, que é o mais popular.

Lembra que eu disse que um bit não significa nada por si só? Agora é o momento de trabalharmos em cima disto!

Temos uma sequência de 4 bits. Sabemos que para números unsigned, temos um total de 15 diferentes sequências de bits, onde cada uma representa um número diferente. Agora pense, temos uma sequência de 4 bits, e agora passamos a representar não só positivos, mas valores negativos também, a minha interpretação sobre estas sequências precisa mudar.

O bit mais a esquerda determina se o valor é positivo ou negativo. Se o bit for igual a 1, o resultado final será negativo. Se for 0, valor final será positivo. Na prática, quando estamos trabalhando com signed numbers, ao invés de calcular da seguinte forma x times 2^i, calculamos da desta forma o último bit: x times -2^i.

Considere o seguinte exemplo:

1 x 2^0 = 10 x 2^1 = 00 x 2^2 = 01 x -2^3 = -8-8 + 0 + 0 + 1 = -7

A forma que interpretamos o último bit mudou. Calculamos ele de forma diferente de como faziamos antes. Graças a isto somos capazes de representar números negativos também!

Detalhes

Eu me referi a uma cadeia de bits como sequência de bits, mas o termo comum é bit vector.

signed numbers pode representar apenas metade do que os unsigned numbers. Isto porque não aumentamos ou diminuimos a quantidade de bits, apenas pegamos os mesmos bits e mudamos a nossa interpretação em relação a eles. Considere:

MAX usigned = 15;
MIN usigned = 0;
MAX signed = 7;
MIN signed = -8;

O valor máximo positivo para signed é 7 e não 8 porque esta sendo considerado também.

Para que fique de fácil visualização, imagine uma casa. A casa é grande, porém decimos dividir os comôdos entre duas pessoas. Ainda é a mesma casa, mas pessoa X tem acesso a menos espaço que antes agora que Y esta presente.

Conclusão

Como sempre, eu não considero minha explicação adequada como a de um professor, mas espero que ao menos uma pessoa tenha apreciado o que eu trouxe.

Agradeço pela a leitura até aqui!