Wraparound de unsigned em C

Imagine que você precisa escrever um código que imprima os números de 10 até 0. Como não é preciso exibir valores negativos, você opta por usar o tipo unsigned (a variável i) num for:

Um código em C que nunca para de executar.

Ao executar o código, ele entra num loop; passa pelo zero diversas vezes e não termina. Qual é o problema? Para entendermos, vamos ver neste post o que é o tipo unsigned e como o wraparound ocorre em C.

Inteiros sem sinal

Todo tipo inteiro representa um intervalo finito (limite) de inteiros definido pela implementação. Inteiro sem sinal pode representar apenas zero ou valor positivo. O C padrão fornece um header (limits.h) com os valores representáveis dos tipos inteiros. Por depender da implementação, é recomendado usá-lo. O código abaixo imprime o maior valor representável do tipo int (2147483647 aqui):

Maior valor representável com o tipo int.

A representação do valor, isto é, a codificação dos bits na memória, num unsigned é bem simples, tirando o padding, os bits que não são usados: é o sistema binário puro, onde cada bit é uma potência de dois e sua soma é o valor. O número 5 poderia ser representado em 4 bits como 0101:

0101 = 2^2 + 2^1 = 5
 | |
 |  ` 2^0 = 1
  ` 2^2 = 4

Todo tipo, exceto char (depende da implementação; não é garantido que char seja unsigned ou signed), é signed por padrão. Para um inteiro sem sinal, podemos escrever unsigned int ou apenas unsigned. Outros tipos como long e long long também aceitam o unsigned: unsigned long long, por exemplo.

Usamos o tipo unsigned geralmente quando queremos representar grandes quantias e valores negativos não são requeridos. Por vezes o unsigned tem precisão maior que signed, pois não utiliza nenhum bit para sinal.

Comparação entre o valor máximo representável de int com e sem sinal.

Wraparound

O wraparound ocorre quando se tenta representar um valor muito pequeno (negativo) ou muito grande (maior que o tipo pode representar) numa variável de tipo unsigned. Via aritmética modular, wraparound reduz o valor ao módulo da largura de bits do tipo. É um comportamento bem definido no C padrão.

Exemplos de wraparound quando ultrapassa o valor máximo e quando é negativo.

Ocorre dois wraparound no código acima: ultrapassando o limite máximo (quando efetuado UINT_MAX + 1) e o mínimo (quando -1). No meu sistema, o programa exibe:

uint_max = 4294967295, uint_min = 0
uint_max + 1 = 0
uint_min - 1 = 4294967295

Aritmética modular

O valor após o wraparound é resultado de uma conta simples de módulo. O módulo faz o número retroceder a um valor, sempre ficando entre um limite. Pense numa lista [0, 1, 2, 3]. Há quatro elementos e o último fica no índice 3. Com módulo, tornamos circular o acesso a essa lista:

lista = [0, 1, 2, 3]
lista[2 % 4]  # 2
lista[5 % 4]  # 1, pois após 3, ele volta ao primeiro e vai mais um
lista[-1 % 4] # 3, vai para o último

Na linguagem C, o módulo é feito com a largura de bits do tipo. Voltando ao exemplo dos 4 bits anterior (0101 = 5), a largura para um tipo de 4 bits seria 2⁴ = 16. O maior número que esse tipo poderia representar seria 2⁴-1 = 15. Quando tentamos representar o número 16, por exemplo, ele passa do limite que é 0..15 e volta ao zero. O mesmo ocorre quando usamos um número negativo, como -1, que vai para 15.

16 % 16 = 0
-1 % 16 = 15

No meu sistema, a largura de bits de um unsigned é 32, sendo 4294967295 o maior valor possível; 0, o menor. Os valores, portanto, mostrado no programa anterior seguem essas duas contas modulares:

4294967295 + 1 % 4294967296 = 0
-1 % 4294967296             = 4294967295

O problema do código

O problema do código torna-se bem simples quando pensamos que o tipo unsigned não permite valores negativos. Dessa forma, a expressão >= 0 sempre é verdadeira, pois nunca o unsigned vai ser -1 para torná-la falsa (ele volta para o maior valor possível até chegar em zero e fica nesse loop).

O for há três partes: inicialização, que é executado apenas uma vez; o teste, que é executado logo após a inicialização e a atualização, que é executada quando o teste não falha. Quando i chega em zero, o teste ainda da verdadeiro, afinal 0 é igual a zero (0 >= 0 é verdadeiro), então i é decrementado, mas ocorre um wraparound e i se torna um número grande, ficando em loop.

Podemos testar que o valor passa a ser -1 no fim do for usando um tipo signed:

Um loop para exibir os valores de 10..0; inclui -1 ao final para o nosso debug.

Ao executar, temos (omiti a saída completa com …):

10
9
...
1
0
-1

Não existe uma solução fácil usando unsigned, o melhor a se fazer é trocar o tipo no for: for(int i = 10; i >= 0; i--).