Se um número é muito grande, ele se espalha para o próximo local de memória?

30

Eu estive revisando a programação C e há apenas algumas coisas me incomodando.

Vamos pegar este código, por exemplo:

int myArray[5] = {1, 2, 2147483648, 4, 5};
int* ptr = myArray;
int i;
for(i=0; i<5; i++, ptr++)
    printf("\n Element %d holds %d at address %p", i, myArray[i], ptr);

Eu sei que um int pode conter um valor máximo de 2.147.483.647 positivo. Então, analisando isso, ele "transborda" para o próximo endereço de memória que faz com que o elemento 2 apareça como "-2147483648" nesse endereço? Mas isso realmente não faz sentido, porque, na saída, ele ainda diz que o próximo endereço contém o valor 4, depois 5. Se o número tivesse transbordado para o próximo endereço, isso não mudaria o valor armazenado nesse endereço? ?

Lembro-me vagamente da programação no MIPS Assembly e de observar os endereços mudarem valores durante o programa passo a passo que os valores atribuídos a esses endereços mudariam.

A menos que eu esteja lembrando incorretamente, eis outra pergunta: se o número atribuído a um endereço específico for maior que o tipo (como em myArray [2]), isso não afetará os valores armazenados no endereço subseqüente?

Exemplo: temos int myNum = 4 bilhões no endereço 0x10010000. É claro que o myNum não pode armazenar 4 bilhões, por isso aparece como um número negativo nesse endereço. Apesar de não poder armazenar esse número grande, ele não afeta o valor armazenado no endereço subsequente de 0x10010004. Corrigir?

Os endereços de memória têm apenas espaço suficiente para armazenar determinados tamanhos de números / caracteres e, se o tamanho ultrapassar o limite, ele será representado de maneira diferente (como tentar armazenar 4 bilhões no int, mas aparecerá como um número negativo) e portanto, não afeta os números / caracteres armazenados no próximo endereço.

Desculpe se eu fui ao mar. Eu tenho tido um grande peido cerebral o dia todo com isso.

atarracado
fonte
10
Você pode estar ficando confuso com excedentes de string .
Robbie Dee
19
Lição de casa: modifique uma CPU simples para que ela se espalhe. Você verá que a lógica se torna muito mais complexa, tudo por um "recurso" que garantiria brechas de segurança em qualquer lugar sem ser útil em primeiro lugar.
Phihag
4
Se você precisar de números realmente grandes, é possível ter uma representação numérica que aumente a quantidade de memória usada para ajustar números grandes. O próprio processador não pode fazer isso, e não é um recurso da linguagem C, mas uma biblioteca pode implementá-lo - uma biblioteca C comum é a biblioteca aritmética GNU Multiple Precision . A biblioteca precisa gerenciar a memória para armazenar os números que possuem um custo de desempenho além da aritmética. Muitos idiomas têm esse tipo de coisa embutido (o que não evita os custos).
precisa saber é o seguinte
11
escreva um teste simples, eu não sou um programador C, mas algo parecido com o int c = INT.MAXINT; c+=1;que aconteceu com c.
Jonh
2
@ JonH: O problema é que estouro no comportamento indefinido. O compilador CA pode identificar esse código e deduzir que é um código inacessível porque ele transborda incondicionalmente. Como o código inacessível não importa, ele pode ser eliminado. Resultado final: nenhum código restante.
precisa saber é o seguinte

Respostas:

48

Não, não tem. Em C, as variáveis ​​têm um conjunto fixo de endereços de memória para trabalhar. Se você estiver trabalhando em um sistema com 4 bytes intse definir uma intvariável como 2,147,483,647e depois adicionar 1, a variável geralmente conterá -2147483648. (Na maioria dos sistemas. O comportamento é realmente indefinido.) Nenhum outro local de memória será modificado.

Em essência, o compilador não permitirá que você atribua um valor muito grande para o tipo. Isso irá gerar um erro do compilador. Se você forçar com um caso, o valor será truncado.

Observado de maneira bit a bit, se o tipo puder armazenar apenas 8 bits e você tentar forçar o valor 1010101010101com um caso, você terminará com os 8 bits inferiores, ou 01010101.

No seu exemplo, independentemente do que você faça myArray[2], myArray[3]conterá '4'. Não há "transbordamento". Você está tentando colocar algo com mais de 4 bytes, apenas cortando tudo na parte alta, deixando os 4 bytes inferiores. Na maioria dos sistemas, isso resultará em -2147483648.

Do ponto de vista prático, você deseja apenas garantir que isso nunca aconteça. Esses tipos de transbordamentos geralmente resultam em defeitos difíceis de resolver. Em outras palavras, se você acha que existe alguma chance de todos os seus valores estarem em bilhões, não use int.

Gort the Robot
fonte
52
Se você estiver trabalhando em um sistema com entradas de 4 bytes e definir uma variável int como 2.147.483.647 e adicionar 1, a variável conterá -2147483648. => Não , é Comportamento indefinido ; portanto, ele pode se repetir ou fazer algo completamente diferente; Eu vi compiladores otimizar verificações com base na ausência de estouro e tem loops infinitos, por exemplo ...
Matthieu M.
Desculpe, sim, você está correto. Eu deveria ter adicionado um "normalmente" lá.
Gort the Robot
@ MatthieuM do ponto de vista da linguagem , isso é verdade. Em termos de execução em um determinado sistema, do que estamos falando aqui, é um absurdo absoluto.
hobbs
@ Hobbs: O problema é que, quando os compiladores manipulam o programa por causa de Comportamento indefinido, a execução do programa realmente produz um comportamento inesperado, comparável com a substituição de memória.
Matthieu M. 21/01
24

Estouro de número inteiro assinado é um comportamento indefinido. Se isso acontecer, seu programa é inválido. O compilador não precisa verificar isso para você; portanto, ele pode gerar um executável que parece fazer algo razoável, mas não há garantia de que isso acontecerá.

No entanto, o estouro de número inteiro não assinado está bem definido. Ele envolverá o módulo UINT_MAX + 1. A memória não ocupada por sua variável não será afetada.

Consulte também https://stackoverflow.com/q/18195715/951890

Vaughn Cato
fonte
estouro de número inteiro assinado é tão bem definido quanto estouro de número inteiro não assinado. se a palavra tiver $ N $ bits, o limite superior do estouro de número inteiro assinado será de $$ 2 ^ {N-1} -1 $$ (onde está em torno de $ -2 ^ {N-1} $), enquanto o o limite superior para o excesso de número inteiro não assinado é de $$ 2 ^ N - 1 $$ (onde envolve em torno de $ 0 $). mesmos mecanismos de adição e subtração, o mesmo tamanho do intervalo de números ($ 2 ^ N $) que pode ser representado. apenas um limite diferente de estouro.
Robert Bristow-johnson
11
@ robertbristow-johnson: Não de acordo com o padrão C.
Vaughn Cato
bem, às vezes os padrões são anacrônicos. olhando para a referência de SO, há um comentário que a atinge diretamente: "A observação importante aqui, porém, é que não existem arquiteturas no mundo moderno usando nada além da aritmética assinada do complemento de 2. Que os padrões de linguagem ainda permitem a implementação por exemplo, um PDP-1 é um artefato histórico puro. - Andy Ross 12/08/13 às 20:12 "
robert bristow-johnson
suponho que não esteja no padrão C, mas suponho que possa haver uma implementação em que a aritmética binária regular não seja usada int. Suponho que eles poderiam usar o código Gray ou BCD ou EBCDIC . não sei por que alguém projetaria hardware para fazer aritmética com código Gray ou EBCDIC, mas, novamente, não sei por que alguém faria unsignedcom binário e assinaria intcom qualquer coisa que não fosse o complemento do 2.
22416 Robert bristow-johnson
14

Então, existem duas coisas aqui:

  • o nível da linguagem: quais são as semânticas de C
  • o nível da máquina: quais são as semânticas do assembly / CPU que você usa

No nível do idioma:

Em C:

  • overflow e underflow são definidos como módulo aritmético para números inteiros não assinados , portanto, o valor "loops"
  • overflow e underflow são Comportamento indefinido para números inteiros assinados , portanto, tudo pode acontecer

Para aqueles que gostariam de um exemplo "que qualquer coisa", eu já vi:

for (int i = 0; i >= 0; i++) {
    ...
}

transformar-se em:

for (int i = 0; true; i++) {
    ...
}

e sim, é uma transformação legítima.

Isso significa que há realmente riscos potenciais de sobrescrever memória em excesso devido a alguma transformação estranha do compilador.

Nota: em Clang ou gcc, use -fsanitize=undefinedem Debug para ativar o Undefined Behavior Sanitizer, que interromperá o estouro / excesso de números inteiros assinados.

Ou significa que você pode substituir a memória usando o resultado da operação para indexar (desmarcada) em uma matriz. Infelizmente, isso é muito mais provável na ausência de detecção de estouro / estouro.

Nota: em Clang ou gcc, use -fsanitize=addressem Debug para ativar o Address Sanitizer, que interromperá o acesso fora dos limites.


No nível da máquina :

Realmente depende das instruções de montagem e da CPU que você usa:

  • no x86, o ADD usará 2 complementos no estouro / abaixo do fluxo e definirá o OF (Sinal de estouro)
  • no futuro CPU da fábrica, haverá 4 modos de estouro diferentes para Add:
    • Módulo: módulo de 2 complementos
    • Armadilha: uma armadilha é gerada, interrompendo a computação
    • Saturar: o valor fica bloqueado para min no underflow ou max no overflow
    • Largura dupla: o resultado é gerado em um registro de largura dupla

Observe que, se as coisas acontecem nos registradores ou na memória, em nenhum dos casos a CPU substitui a memória durante o estouro.

Matthieu M.
fonte
Os três últimos modos estão assinados? (Não importa para o primeiro, pois possui 2 complementos.) #
Deduplicator
11
@ Reduplicador: De acordo com a Introdução ao modelo de programação da CPU do moinho, existem diferentes opcodes para adição assinada e adição não assinada; Espero que ambos os opcodes suportem os 4 modos (e possam operar em vários bits de largura e escalares / vetores). Então, novamente, é hardware vapor por agora;)
Matthieu M.
4

Para responder melhor à @ StevenBurnap, a razão pela qual isso acontece é a maneira como os computadores funcionam no nível da máquina.

Sua matriz é armazenada na memória (por exemplo, na RAM). Quando uma operação aritmética é executada, o valor na memória é copiado nos registros de entrada do circuito que executa a aritmética (a ALU: Unidade Lógica Aritmética ), a operação é executada nos dados nos registros de entrada, produzindo um resultado no registro de saída. Esse resultado é então copiado de volta para a memória no endereço correto na memória, deixando outras áreas da memória intocadas.

Pharap
fonte
4

Primeiro (assumindo o padrão C99), convém incluir <stdint.h>o cabeçalho padrão e usar alguns dos tipos aqui definidos, principalmente o int32_tque é exatamente um número inteiro assinado de 32 bits ou o uint64_tque é exatamente um número inteiro não assinado de 64 bits, e assim por diante. Você pode usar tipos como int_fast16_tpor motivos de desempenho.

Leia as respostas de outras pessoas explicando que a aritmética não assinada nunca é derramada (ou transborda) para locais de memória adjacentes. Cuidado com o comportamento indefinido no estouro assinado .

Então, se você precisar calcular exatamente números inteiros enormes (por exemplo, você deseja calcular fatorial de 1000 com todos os seus 2568 dígitos em decimal), você deseja bigints, também conhecidos como números de precisão arbitrários (ou números). Os algoritmos para uma aritmética bigint eficiente são muito inteligentes e geralmente requerem o uso de instruções especializadas da máquina (por exemplo, alguns adicionam palavras com carry, se o seu processador tiver isso). Por isso, recomendo fortemente, nesse caso, usar alguma biblioteca bigint existente como o GMPlib

Basile Starynkevitch
fonte