A subtração de inteiros sem sinal é um comportamento definido?

100

Encontrei o código de alguém que parece acreditar que há um problema ao subtrair um inteiro sem sinal de outro inteiro do mesmo tipo quando o resultado seria negativo. Portanto, esse código como este estaria incorreto mesmo se funcionar na maioria das arquiteturas.

unsigned int To, Tf;

To = getcounter();
while (1) {
    Tf = getcounter();
    if ((Tf-To) >= TIME_LIMIT) {
        break;
    } 
}

Esta é a única citação vagamente relevante do padrão C que pude encontrar.

Um cálculo envolvendo operandos sem sinal nunca pode transbordar, porque um resultado que não pode ser representado pelo tipo inteiro sem sinal resultante é o módulo reduzido do número que é um maior que o maior valor que pode ser representado pelo tipo resultante.

Suponho que essa citação possa significar que, quando o operando certo é maior, a operação é ajustada para ser significativa no contexto de números de módulo truncados.

ie

0x0000 - 0x0001 == 0x 1 0000 - 0x0001 == 0xFFFF

ao contrário de usar a semântica assinada dependente da implementação:

0x0000 - 0x0001 == (sem sinal) (0 + -1) == (0xFFFF mas também 0xFFFE ou 0x8001)

Qual ou qual interpretação está certa? Está definido de alguma forma?

LihO
fonte
3
A escolha de palavras no padrão é lamentável. Que “nunca pode transbordar” significa que não é uma situação de erro. Usando a terminologia do padrão, em vez de estourar o valor "embrulha".
danorton

Respostas:

107

O resultado de uma subtração que gera um número negativo em um tipo sem sinal é bem definido:

  1. [...] Um cálculo envolvendo operandos sem sinal nunca pode estourar, porque um resultado que não pode ser representado pelo tipo inteiro sem sinal resultante é o módulo reduzido do número que é um maior que o maior valor que pode ser representado pelo tipo resultante. (ISO / IEC 9899: 1999 (E) §6.2.5 / 9)

Como você pode ver, (unsigned)0 - (unsigned)1é igual a -1 módulo UINT_MAX + 1, ou em outras palavras, UINT_MAX.

Observe que, embora diga "Um cálculo envolvendo operandos sem sinal nunca pode estourar", o que pode levar você a acreditar que se aplica apenas para exceder o limite superior, isso é apresentado como uma motivação para a parte de ligação real da frase: "a resultado que não pode ser representado pelo tipo inteiro sem sinal resultante é módulo reduzido o número que é um maior do que o maior valor que pode ser representado pelo tipo resultante. " Essa frase não se restringe ao estouro do limite superior do tipo e se aplica igualmente a valores muito baixos para serem representados.

bdonlan
fonte
2
Obrigado! Agora vejo a interpretação que estava faltando. Acho que eles poderiam ter escolhido uma redação mais clara.
4
Eu me sinto muito melhor agora, sabendo que se alguma adição sem sinal chegar a zero e causar o caos, será porque uintsempre teve a intenção de representar o anel matemático dos inteiros 0por meio UINT_MAX, com as operações de módulo de adição e multiplicação UINT_MAX+1, e não porque de um estouro. No entanto, isso levanta a questão de por que, se os anéis são um tipo de dados tão fundamental, a linguagem não oferece suporte mais geral para anéis de outros tamanhos.
Theodore Murdock
2
@TheodoreMurdock Acho que a resposta a essa pergunta é simples. Até onde sei, o fato de ser um anel é uma consequência, não uma causa. O requisito real é que os tipos sem sinal devem ter todos os seus bits participando da representação do valor. O comportamento semelhante a um anel flui naturalmente disso. Se você deseja tal comportamento de outros tipos, faça sua aritmética seguida de aplicação do módulo necessário; que usa operadores fundamentais.
sublinhado_d
@underscore_d Claro ... é claro porque eles tomaram a decisão de design. É simplesmente divertido que eles escreveram as especificações aproximadamente como "não há excesso / insuficiência aritmética porque o tipo de dados é especificado como um anel", como se esta escolha de design significasse que os programadores não precisariam evitar cuidadosamente -fluxo ou seus programas falham espetacularmente.
Theodore Murdock
120

Quando você trabalha com tipos não assinados , a aritmética modular (também conhecida como comportamento "wrap around" ) está ocorrendo. Para entender essa aritmética modular , basta dar uma olhada nestes relógios:

insira a descrição da imagem aqui

9 + 4 = 1 ( 13 mod 12 ), então para a outra direção é: 1 - 4 = 9 ( -3 mod 12 ). O mesmo princípio é aplicado ao trabalhar com tipos sem sinal. Se o tipo de resultado for unsigned, então a aritmética modular ocorre.


Agora observe as seguintes operações armazenando o resultado como um unsigned int:

unsigned int five = 5, seven = 7;
unsigned int a = five - seven;      // a = (-2 % 2^32) = 4294967294 

int one = 1, six = 6;
unsigned int b = one - six;         // b = (-5 % 2^32) = 4294967291

Quando você quiser ter certeza de que o resultado é signed, armazene-o na signedvariável ou faça o cast signed. Quando você deseja obter a diferença entre os números e certificar-se de que a aritmética modular não será aplicada, você deve considerar o uso de abs()funções definidas em stdlib.h:

int c = five - seven;       // c = -2
int d = abs(five - seven);  // d =  2

Tenha muito cuidado, especialmente ao escrever as condições, porque:

if (abs(five - seven) < seven)  // = if (2 < 7)
    // ...

if (five - seven < -1)          // = if (-2 < -1)
    // ...

if (one - six < 1)              // = if (-5 < 1)
    // ...

if ((int)(five - seven) < 1)    // = if (-2 < 1)
    // ...

mas

if (five - seven < 1)   // = if ((unsigned int)-2 < 1) = if (4294967294 < 1)
    // ...

if (one - six < five)   // = if ((unsigned int)-5 < 5) = if (4294967291 < 5)
    // ...
LihO
fonte
4
Legal com os relógios, embora a prova tornasse esta a resposta correta. A premissa da pergunta já inclui a afirmação de que tudo isso pode ser verdade.
Lightness Races in Orbit
5
@LightnessRacesinOrbit: Obrigado. Escrevi porque acho que alguém pode achar muito útil. Eu concordo, que não é uma resposta completa.
LihO
4
A linha int d = abs(five - seven);não é boa. Primeiro five - sevené calculado: a promoção deixa os tipos de operando como unsigned int, o resultado é calculado como módulo (UINT_MAX+1)e avalia para UINT_MAX-1. Então, esse valor é o parâmetro real para abs, o que é uma má notícia. abs(int)causa um comportamento indefinido passando o argumento, uma vez que não está no intervalo e abs(long long)provavelmente pode conter o valor, mas o comportamento indefinido ocorre quando o valor de retorno é coagido inta inicializar d.
Ben Voigt,
1
@LihO: O único operador em C ++ que é sensível ao contexto e atua de forma diferente dependendo de como seu resultado é usado é um operador de conversão personalizado operator T(). A adição nas duas expressões que estamos discutindo é realizada em tipo unsigned int, com base nos tipos de operando. O resultado da adição é unsigned int. Em seguida, esse resultado é convertido implicitamente para o tipo necessário no contexto, uma conversão que falha porque o valor não é representável no novo tipo.
Ben Voigt,
1
@LihO: Pode ajudar pensar em double x = 2/3;vsdouble y = 2.0/3;
Ben Voigt
5

Bem, a primeira interpretação está correta. No entanto, seu raciocínio sobre a "semântica assinada" neste contexto está errado.

Novamente, sua primeira interpretação está correta. A aritmética sem sinal segue as regras da aritmética de módulo, o que significa que 0x0000 - 0x0001avalia para 0xFFFFtipos sem sinal de 32 bits.

No entanto, a segunda interpretação (aquela baseada na "semântica com sinais") também é necessária para produzir o mesmo resultado. Ou seja, mesmo que você avalie 0 - 1no domínio do tipo assinado e obtenha -1como resultado intermediário, isso -1ainda é necessário para produzir 0xFFFFquando, posteriormente, for convertido para o tipo não assinado. Mesmo que alguma plataforma use uma representação exótica para inteiros com sinal (complemento de 1, magnitude com sinal), essa plataforma ainda é obrigada a aplicar regras de aritmética do módulo ao converter valores inteiros com sinal em valores sem sinal.

Por exemplo, esta avaliação

signed int a = 0, b = 1;
unsigned int c = a - b;

ainda tem a garantia de produzir UINT_MAXem c, mesmo se a plataforma estiver usando uma representação exótica para inteiros assinados.

Formiga
fonte
4
Acho que você quer dizer tipos sem sinal de 16 bits, não de 32 bits.
xioxox,
4

Com números sem sinal de tipo unsigned intou maiores, na ausência de conversões de tipo, a-bé definido como o número sem sinal que, quando adicionado b, renderá a. A conversão de um número negativo em sem sinal é definida como o resultado do número que, quando adicionado ao número original com sinal invertido, renderá zero (portanto, converter -5 em sem sinal renderá um valor que, quando adicionado a 5, resultará em zero) .

Observe que os números sem sinal menores do que unsigned intpodem ser promovidos ao tipo intantes da subtração, o comportamento de a-bdependerá do tamanho de int.

supergato
fonte