Por que o bit-shift não é deixado, “<<”, para inteiros de 32 bits funcionar como esperado quando usado mais de 32 vezes?

Quando eu escrevo o programa a seguir e uso o compilador GNU C ++, a saída é 1 que eu acho que é devido à operação de rotação executada pelo compilador.

 #include  int main() { int a = 1; std::cout << (a << 32) << std::endl; return 0; } 

Mas logicamente, como se diz que os bits são perdidos se eles transbordarem a largura do bit, a saída deve ser 0. O que está acontecendo?

O código está em ideone, http://ideone.com/VPTwj .

    Isso é causado devido a uma combinação de um comportamento indefinido em C e o fato de que o código gerado para processadores IA-32 tem uma máscara de 5 bits aplicada na contagem de turnos. Isso significa que nos processadores IA-32, o intervalo de uma contagem de turnos é de 0 a 31 apenas. 1

    Da linguagem de programação C 2

    O resultado é indefinido se o operando direito for negativo ou maior que ou igual ao número de bits no tipo da expressão esquerda.

    De IA-32 Manual do Desenvolvedor de Software da Arquitetura Intel 3

    O 8086 não mascara a contagem de turnos. No entanto, todos os outros processadores IA-32 (começando com o processador Intel 286) mascaram a contagem de mudança para 5 bits, resultando em uma contagem máxima de 31. Esse mascaramento é feito em todos os modos operacionais (incluindo o modo 8086 virtual) para reduzir o tempo máximo de execução das instruções.


    1 http://codeyarns.com/2004/12/20/c-shift-operator-mayhem/

    2 A7.8 Operadores de deslocamento, Apêndice A. Manual de referência, A linguagem de programação C

    3 SAL / SAR / SHL / SHR – Shift, Capítulo 4. Referência do Conjunto de Instruções, IA-32 Manual do Desenvolvedor de Software da Arquitetura Intel

    Em C ++, shift só é bem definido se você alterar um valor a menos que o tamanho do tipo. Se int é de 32 bits, então apenas 0 a e incluindo 31 passos é bem definido.

    Então, por que isso?

    Se você der uma olhada no hardware subjacente que executa a mudança, se ele só tiver que examinar os cinco bits inferiores de um valor (no caso de 32 bits), ele poderá ser implementado usando menos portas lógicas do que se ele tiver que inspecionar cada bit do valor.

    Responda para questionar em comentário

    C e C ++ são projetados para rodar o mais rápido possível, em qualquer hardware disponível. Hoje, o código gerado é simplesmente uma instrução ” shift ”, independentemente de como o hardware subjacente lida com valores fora do intervalo especificado. Se os idiomas tivessem especificado como o turno deveria se comportar, o gerado poderia ter que verificar se a contagem de turnos está dentro do intervalo antes de realizar o turno. Normalmente, isso produziria três instruções (comparar, ramificar, deslocar). (É verdade que, neste caso, não seria necessário, pois a contagem de turnos é conhecida.)

    É um comportamento indefinido de acordo com o padrão C ++:

    O valor de E1 < < E2 é E1 posições de bit E2 deslocadas para a esquerda; os bits desocupados são preenchidos com zero. Se E1 tiver um tipo não assinado, o valor do resultado será E1 × 2 ^ E2, módulo reduzido um a mais que o valor máximo representável no tipo de resultado. Caso contrário, se E1 tiver um tipo assinado e um valor não negativo, e E1 × 2 ^ E2 for representável no tipo de resultado, então esse é o valor resultante; caso contrário, o comportamento é indefinido .

    As respostas de Lindydancer e 6502 explicam porque (em algumas máquinas) é 1 que está sendo impresso (embora o comportamento da operação seja indefinido). Estou adicionando os detalhes caso eles não sejam óbvios.

    Estou assumindo que (como eu) você está executando o programa em um processador Intel. O GCC gera estas instruções de assembly para a operação de turno:

     movl $32, %ecx sall %cl, %eax 

    No tópico de sall e outras operações de turno, a página 624 no Manual de Referência do Conjunto de Instruções diz:

    O 8086 não mascara a contagem de turnos. No entanto, todos os outros processadores da arquitetura Intel (começando com o processador Intel 286) mascaram a contagem de mudança para cinco bits, resultando em uma contagem máxima de 31. Esse mascaramento é feito em todos os modos operacionais (incluindo o modo 8086 virtual) para reduzir o tempo máximo de execução das instruções.

    Como os 5 bits inferiores de 32 são zero, então 1 < < 32 é equivalente a 1 < < 0 , que é 1 .

    Experimentando com números maiores, poderíamos prever que

     cout < < (a << 32) << " " << (a << 33) << " " << (a << 34) << "\n"; 

    iria imprimir 1 2 4 , e de fato é isso que está acontecendo na minha máquina.

    Não funciona como esperado porque você está esperando muito.

    No caso do x86, o hardware não se importa com as operações de deslocamento, onde o contador é maior que o tamanho do registrador (veja, por exemplo, a descrição da instrução SHL na documentação de referência x86 para uma explicação).

    O padrão C ++ não queria impor um custo extra dizendo o que fazer nesses casos, porque o código gerado teria sido forçado a adicionar verificações extras e lógica para cada turno paramétrico.

    Com essa liberdade, os implementadores de compiladores podem gerar apenas uma instrução de assembly sem qualquer teste ou ramificação.

    Uma abordagem mais “útil” e “lógica” teria sido, por exemplo, ter (x < < y) equivalente a (x >> -y) e também o tratamento de contadores altos com um comportamento lógico e consistente.

    No entanto, isso exigiria um tratamento muito mais lento para a mudança de bit, portanto, a escolha era fazer o que o hardware faz, deixando aos programadores a necessidade de escrever suas próprias funções para casos secundários.

    Dado que o hardware diferente faz coisas diferentes nestes casos o que a norma diz é basicamente "O que acontece quando você faz coisas estranhas simplesmente não culpe C ++, a culpa é sua" traduzida em legalês.

    A mudança de uma variável de 32 bits por 32 ou mais bits é um comportamento indefinido e pode fazer com que o compilador faça com que os daemons saiam do seu nariz.

    Sério, na maioria das vezes a saída será 0 (se int for de 32 bits ou menos), uma vez que você está mudando o 1 até que ele caia novamente e nada além de 0 será deixado. Mas o compilador pode otimizá-lo para fazer o que quiser.

    Veja a excelente input no blog do LLVM O que todo programador C deve saber sobre o comportamento indefinido , uma leitura obrigatória para todos os desenvolvedores de C.

    Já que você está mudando um int em 32 bits; você receberá: warning C4293: '< <' : shift count negative or too big, undefined behavior em VS. Isso significa que você está mudando além do número inteiro e a resposta pode ser QUALQUER COISA, porque é um comportamento indefinido.

    Você poderia tentar o seguinte. Isso realmente dá a saída como 0 após 32 deslocamentos para a esquerda.

     #include #include using namespace std; int main() { int a = 1; a < <= 31; cout << (a <<= 1); return 0; } 

    Eu tive o mesmo problema e isso funcionou para mim:

    f = ((long long) 1 < < (i-1));

    Onde eu posso ser qualquer inteiro maior que 32 bits. O 1 tem que ser um inteiro de 64 bits para o deslocamento para o trabalho.