Inteiros de tamanho fixo com e sem sinal

Operações aritméticas em Python puro funcionam de maneira bem diferente de funções aritméticas usando Numpy, Cython ou Numba. Diferentemente de linguagens de baixo nível como C, variáveis inteiras em Python não tem relação com tipos de dados usados pelo processador para realizar aritmética. Logo, um inteiro Python pode conter valores arbitrariamente longos e não existe diferenciação entre variáveis com ou sem sinal. No caso de variáveis decimais, a precisão sempre é dupla, equivalendo a uma variável tipo double em C. Em geral, isto torna a escrita de programas mais simples (e possivelmente mais segura) ao evitar erros de overflow e underflow, principalmente com variáveis que representados índices, contadores ou tamanhos de memória.

O exemplo abaixo ilustra este fenômeno ao criar um escalar com Numpy usando um inteiro com 8 bits sem sinal.

import numpy as np

purepy_int = 255
np_int8 = np.zeros(1, np.uint8)
np_int8[0] = 255
print(purepy_int, np_int8[0])
purepy_int += 1
np_int8 += 1
print('Após +1', purepy_int, np_int8[0])

255 255
Após +1 256 0

Apesar de mais simples, a abordagem usada em Python puro é mais lenta. Na verdade, ela é MUITO mais lenta do que utilizar tipos de dados ligados a CPU e este é um dos principais motivos da existência de bibliotecas como Numba e Cython. Neste texto irei explorar um pouco de como inteiros são representados na CPU e quais cuidados devem ser observados ao programar usando tipos de dados nativos ao invés de inteiros em Python puro.

Representação de números em diferentes bases

Computadores trabalham com uma representação de tamanho fixo para números inteiros (e decimais) baseada no número de dígitos necessários para representá-lo. Diferentemente de nossa álgebra cotidiana, em que possuimos 10 algarismos (base decimal), CPUs usam apenas 2 algarismos (base binária).

Não importa a base utilizada, a contagem é feita da mesma maneira que fazemos usando a base decimal. Porém, usamos somente os algarismos disponíveis na base que estamos usando. Veja abaixo uma sequência de números na base binária (2) e seu equivalente na base decimal.

• 0 => 0
• 1 => 1
• 2 => 10
• 3 => 11
• 4 => 100
• 5 => 101

Apesar da base ser diferente, a adição funciona da mesma maneira. Sempre que os algarismos disponíveis em um dígito se esgotam (chegam até \(b\)), adicionamos \(1\) ao digito à esquerda e atribuimos \(0\) ao dígito atual. Porém, cada dígito representa uma potência de \(b\) ao invés de uma potência de \(10\). No exemplo acima, quando passamos de \(11\) (3) para \(100\) (4) fazemos esta operação duas vezes e saímos de \(1 \times 2^0 + 1 \times 2^1 = 3\) para \(0 \times 2^0 + 0 \times 2^1 + 1 \times 2^2 = 4\).

Podemos também usar bases com mais algarismos que 10, como a hexadecimal (base 16, contém números 0...9 e letras A..F). Veja abaixo uma sequência de números em hexadecimal. É usual adicionar o prefixo 0x ao escrever números em hexadecimal. As mesmas propriedades citadas acima para números binários são válidas para números hexadecimais.

• 0x9 => 9
• 0xA => 10
• 0xB => 11
• 0xF => 15
• 0x10 => 16

A conversão de números em uma base \(b\) para a base decimal é bastante simples. Sejam \(n_0, \dots, n_m\) os dígitos de um número representado na base \(b\) (ou seja, \(0 \leq n_i \leq b-1\)) tal que \(n_0\) é o dígito mais à direita e \(n_m\) é o dígito mais à esquerda. Este número pode ser convertido para o número \(n^{(10)}\) em base decimal usando a seguinte expressão.

\[\begin{equation} n^{(10)} = \sum_{i=0}^m b^i n_i \end{equation}\]

Como temos \(b\) algarismos, um número em base \(b\) com \(m\) dígitos pode representar \(b^m\) números diferentes. Contando com o zero e assumindo que os números são positivos, o intervalo representado é de números entre \(0\) e \(b^m - 1\).

Vejamos um exemplo com números binários. Seja \(n^{(2)} = 10010011\) um número binário. Sua representação em base decimal é dada por

\[\begin{equation} n^{(10)} = 1 \times 2^0 + 1 \times 2^1 + 0 \times 2^2 + 0 \times 2^3 + 1 \times 2^4 + 0 \times 2^5 + 0 \times 2^6 + 1 \times 2^7 = \textbf{147} \end{equation}\]

A conversão de um número em base decimal para uma base \(b\) é feita realizando sucessivas divisões por \(b\) e utilizando o resto de cada divisão como um dígito. Veja o exemplo abaixo, em que convertemos o número decimal \(147\) para a base binária.

• 147 / 2 = 73, \(n_0 = 1 = (147 \% 2)\)
• 73 / 2 = 36, \(n_1 = 1 = (73 \% 2)\)
• 36 / 2 = 18, \(n_2 = 0 = (36 \% 2)\)
• 18 / 2 = 9, \(n_3 = 0 = (18 \% 2)\)
• 9 / 2 = 4, \(n_4 = 1 = (9 \% 2)\)
• 4 / 2 = 2, \(n_5 = 0 = (4 \% 2)\)
• 2 / 2 = 1, \(n_6 = 0 = (2 \% 2)\)
• 1 / 2 = 0, \(n_7 = 1 = (1 \% 2)\)

A conversão entre bases diferentes pode ser feita primeiro convertendo para decimal e depois convertendo o decimal resultante para a base final.

Inteiros com tamanho fixo

O tamanho nativo do inteiro de cada processador é chamado de word size. Em processadores 64 bits (como todos os Intel e AMD modernos), o word size possui 64 bits (8 bytes). Logo, os registradores do processador (áreas de memória que o processador usa para armazenar parâmetros para as instruções) possuem tamanho de 64bits. Alé disto, este tamanho também é usado para representar endereços de memória. Como os processadores intel modernos são retro-compatíveis, eles também possuem instruções que tratam inteiros de 8, 16 e 32 bits. Logo, temos suporte nativo a inteiros usando todos estes tamanhos. Note, porém, que os números que representamos até agora são sempre positivos, porém em aplicações em geral precisamos usar também números negativos. A maneira que isto é feito em binário é usando uma técnica chamada "complemento de 2" (two's complement).

Antes de tudo, uma solução simples para este problema poderia ser usar o último dígito (mais a esquerda) como um indicador de sinal. Isto traz dois problemas: (i) existem duas representações para o 0 (-0 e +0) (ii) teríamos que usar algoritmos de adição diferentes para inteiros com e sem sinal.

A técnica de two's complement utiliza o bit mais significativo do inteiro como uma potência de 2 negativa. A representação decimal de um número binário com \(m\) dígitos \(n_0, \dots, n_{m-1}\), com \(n_{m-1}\) sendo o bit mais significativo (à esquerda) é

\[\begin{equation} n^{(10)} = -n_{m-1} 2^{m-1} + \sum_{i=0}^{m-2} n_i 2^i \end{equation}\]

Binários em two's complement com m dígitos podem representar inteiros entre \(-2^{m-1}\) e \(2^{m-1} - 1\). Claramente, é necessário sempre saber se o número que estamos representando é um inteiro unsigned (sem sinal) ou signed (com sinal). As operações nativas da CPU podem aplicar algoritmos diferentes no caso de inteiros com ou sem sinal. Mais importante que isto: não armazenamos na memória se o inteiro tem ou não sinal. Esta interpretação depende exclusivamente do programador.

Seja \(m=4\) (inteiros de 4 bits). O valor binário 1001 é interpretado como um inteiro sem sinal de valor 9 e como o inteiro com sinal -7. Se não formos cuidadosos podemos, por acidente, interpretar inteiros com sinal como sem sinal (e vice-versa) e introduzir bugs em nossos programas.

Aritmética com inteiros de tamanho fixo

Um problema da aritmética com inteiros de tamanho fixo é que operações entre dois inteiros sem sinal de tamanho \(m\) podem ocupar mais de \(m\) bits. Ou seja, pode ser que o resultado não caiba em nenhum registrador da CPU. A CPU possui uma śerie de flags que podem ser ativadas ao realizar operações aritméticas e que indicam se um erro ocorreu durante a operação. As flags mais comuns para operações aritméticas estão listadas abaixo.

• CF(Carry Flag) - indica se a adição/subtração sem sinal gerou um resultado maior que o tamanho do registrador (ou menor que 0);
• SF(Sign Flag) - sinal do resultado da operação (para inteiros com sinal);
• OF(Overflow flag) - 1 se o resultado da operação não cabe no registrador de origem (para inteiros com sinal).

As operações de adição (ADD) e subtração (SUB) não fazem diferenciação entre inteiros com ou sem sinal. É responsabilidade do programador checar as flags corretas conforme o tipo de inteiro armazenado. Veja abaixo alguns exemplos de operações e suas interpretações com e sem sinal. Note que operações entre números com sinal diferente nunca podem dar overflow!

Op 1	op 2	Operação	Resultado	Com sinal	Sem sinal	CF	OF	SF
0b11111111	0b00000111	-	0b11111000	255-7=248	-1-7=-8	0	0	1
0b11111111	0b00000111	+	0b00000110	255+7=6	-1+7=6	1	0	0
0b11000000	0b10001000	+	0b01001000	192+136=72	-64+(-120)=72	1	1	0
0b01000001	0b00111111	+	0b10000000	65+63=128	65+63=-128	0	1	1

As operações de multiplicação e divisão possuem variantes para inteiros sem sinal (MUL/DIV) e com sinal (IMUL/IDIV). No caso da multiplicação, as flags OF e CF são setadas se o resultado não couber no tamanho dos registradores usados como operandos. As instruções de divisão não setam flags, mas podem lançar exceções caso ocorra divisão por 0, por exemplo. O funcionamento destas instruções é semelhante ao apresentado acima para adição/subtração.

---

Espero que este texto tenha ajudado a mostrar um pouco de como o processador trata números inteiros. Este conhecimento é muito útil não só quando programamos em linguagens com tipos inteiros de tamanho fixo mas também com bibliotecas numéricas como o Numpy.

Como sempre, dúvidas, comentários e críticas podem ser colocados na seção Comentários abaixo. Só lembre-se sempre de ser gentil ;)