shift - Os operadores de deslocamento(<<,>>) são aritméticos ou lógicos em C?



ou logico (8)

Em C, os operadores de deslocamento ( << , >> ) são aritméticos ou lógicos?


Answer #1

TL; DR

Considere i e n para serem os operandos esquerdo e direito, respectivamente, de um operador de deslocamento; o tipo de i , após promoção inteira, ser T Assumindo que n esteja em [0, sizeof(i) * CHAR_BIT) - indefinidamente - temos estes casos:

| Direction  |   Type   | Value (i) | Result                   |
| ---------- | -------- | --------- | ------------------------ |
| Right (>>) | unsigned |     0    | −∞  (i ÷ 2ⁿ)            |
| Right      | signed   |     0    | −∞  (i ÷ 2ⁿ)            |
| Right      | signed   |    < 0    | Implementation-defined  |
| Left  (<<) | unsigned |     0    | (i * 2ⁿ) % (T_MAX + 1)   |
| Left       | signed   |     0    | (i * 2ⁿ)                |
| Left       | signed   |    < 0    | Undefined                |

† a maioria dos compiladores implementa isso como mudança aritmética
‡ indefinido se o valor ultrapassar o tipo de resultado T; tipo promovido de i

Mudando

A primeira é a diferença entre mudanças lógicas e aritméticas de um ponto de vista matemático, sem se preocupar com o tamanho do tipo de dados. Deslocamentos lógicos sempre preenchem os bits descartados com zeros, enquanto o deslocamento aritmético o preenche com zeros apenas para o deslocamento à esquerda, mas para o deslocamento à direita copia o MSB preservando assim o sinal do operando (assumindo uma codificação de complemento de dois para valores negativos).

Em outras palavras, o deslocamento lógico olha para o operando deslocado como apenas um fluxo de bits e os move, sem se preocupar com o sinal do valor resultante. O deslocamento aritmético olha para ele como um número (assinado) e preserva o sinal quando os turnos são feitos.

Um deslocamento aritmético esquerdo de um número X por n é equivalente a multiplicar X por 2 n e é, portanto, equivalente ao deslocamento lógico esquerdo; uma mudança lógica também daria o mesmo resultado, já que o MSB cai do fim e não há nada a preservar.

Um deslocamento aritmético correto de um número X por n é equivalente a divisão inteira de X por 2 n SOMENTE se X for não negativo! A divisão inteira não é mais do que divisão matemática e round para 0 ( trunc ).

Para números negativos, representados pela codificação de complemento de dois, deslocar para a direita por n bits tem o efeito de dividir matematicamente por 2n e arredondar para −∞ ( floor ); assim, o deslocamento para a direita é diferente para valores não negativos e negativos.

para X ≥ 0, X >> n = X / 2 n = trunc (X ÷ 2 n )

para X <0, X >> n = piso (X ÷ 2 n )

onde ÷ é divisão matemática, / é divisão inteira. Vamos ver um exemplo:

37) 10 = 100101) 2

37 ÷ 2 = 18,5

37/2 = 18 (arredondando 18,5 em direção a 0) = 10010) 2 [resultado do deslocamento direito aritmético]

-37) 10 = 11011011) 2 (considerando um complemento de dois, representação de 8 bits)

-37 ÷ 2 = -18,5

-37 / 2 = -18 (arredondando 18,5 no sentido de 0) = 11101110) 2 [NÃO é o resultado do deslocamento direito aritmético]

-37 >> 1 = -19 (arredondando 18,5 em direção a −∞) = 11101101) 2 [resultado do turno de direita aritmético]

Como Guy Steele apontou , essa discrepância levou a Wikipedia . Aqui, não negativo (matemática) pode ser mapeado para valores não negativos não assinados e assinados (C); ambos são tratados da mesma maneira e os deslocamentos à direita são feitos por divisão inteira.

Assim, lógica e aritmética são equivalentes em deslocamento para a esquerda e para valores não negativos em deslocamento para a direita; está em certo deslocamento de valores negativos que eles diferem.

Tipos de operandos e resultados

Norma C99 §6.5.7 :

Cada um dos operandos deve ter tipos inteiros.

As promoções inteiras são realizadas em cada um dos operandos. O tipo do resultado é o do operando esquerdo promovido. Se o valor do operando direito for negativo ou for maior ou igual à largura do operando esquerdo promovido, o comportamento é indefinido.

short E1 = 1, E2 = 3;
int R = E1 << E2;

No trecho acima, ambos os operandos se tornam int (devido à promoção de inteiro); se E2 foi negativo ou E2 ≥ sizeof(int) * CHAR_BIT então a operação é indefinida. Isso ocorre porque deslocar mais do que os bits disponíveis certamente irá transbordar. Se R tivesse sido declarado como short , o resultado int da operação de turno seria implicitamente convertido em short ; uma conversão de restrição, que pode levar a um comportamento definido pela implementação se o valor não puder ser representado no tipo de destino.

Desvio à esquerda

O resultado de E1 << E2 é E1 posições de bit E2 deslocadas para a esquerda; Os bits vazios são preenchidos com zeros. 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. 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.

Como os turnos da esquerda são os mesmos para ambos, os bits vazios são simplesmente preenchidos com zeros. Em seguida, ele afirma que, para tipos não assinados e assinados, é uma mudança aritmética. Estou interpretando isso como uma mudança aritmética, já que as mudanças lógicas não se importam com o valor representado pelos bits, apenas o vê como um fluxo de bits; mas o padrão não fala em termos de bits, mas definindo-o em termos do valor obtido pelo produto de E1 com 2 E2 .

A ressalva aqui é que, para tipos assinados, o valor deve ser não negativo e o valor resultante deve ser representável no tipo de resultado. Caso contrário, a operação é indefinida. O tipo de resultado seria o tipo do E1 depois de aplicar a promoção integral e não o tipo de destino (a variável que vai manter o resultado). O valor resultante é implicitamente convertido no tipo de destino; se não for representável nesse tipo, então a conversão é definida pela implementação (C99 §6.3.1.3 / 3).

Se E1 é um tipo assinado com um valor negativo, o comportamento da mudança à esquerda é indefinido. Este é um caminho fácil para o comportamento indefinido que pode facilmente passar despercebido.

Deslocamento para a direita

O resultado de E1 >> E2 é E1 deslocadas para a direita nas posições E2. Se E1 tiver um tipo não assinado ou se E1 tiver um tipo assinado e um valor não negativo, o valor do resultado será a parte integral do quociente de E1 / 2 E2 . Se E1 tiver um tipo assinado e um valor negativo, o valor resultante será definido pela implementação.

Deslocamento à direita para valores não negativos não assinados e assinados são bastante diretos; os bits vazios são preenchidos com zeros. Para valores negativos assinados, o resultado da mudança à direita é definido pela implementação. Dito isso, a maioria das implementações, como o GCC e o Visual C ++, implementam o deslocamento para a direita como mudança aritmética, preservando o bit de sinal.

Conclusão

Ao contrário do Java, que tem um operador especial >>> para deslocamento lógico além do usual >> e << , C e C ++ têm apenas mudança aritmética com algumas áreas deixadas indefinidas e definidas pela implementação. A razão pela qual eu os considero como aritmética é devido à formulação padrão da operação matematicamente, em vez de tratar o operando deslocado como um fluxo de bits; esta é talvez a razão pela qual deixa essas áreas un / implementation-defined em vez de apenas definir todos os casos como mudanças lógicas.


Answer #2

Ao mudar para a esquerda, não há diferença entre o deslocamento aritmético e lógico. Ao deslocar para a direita, o tipo de deslocamento depende do tipo do valor que está sendo deslocado.

(Como pano de fundo para aqueles leitores não familiarizados com a diferença, um deslocamento lógico "direito" de 1 bit desloca todos os bits para a direita e preenche o bit mais à esquerda com um 0. Um deslocamento "aritmético" deixa o valor original no bit mais à esquerda A diferença torna-se importante quando se lida com números negativos.)

Ao deslocar um valor não assinado, o operador >> em C é um deslocamento lógico. Ao mudar um valor sinalizado, o operador >> é uma mudança aritmética.

Por exemplo, assumindo uma máquina de 32 bits:

signed int x1 = 5;
assert((x1 >> 1) == 2);
signed int x2 = -5;
assert((x2 >> 1) == -3);
unsigned int x3 = (unsigned int)-5;
assert((x3 >> 1) == 0x7FFFFFFD);

Answer #3

Bem, eu procurei na Wikipédia , e eles têm isto para dizer:

C, no entanto, tem apenas um operador de deslocamento à direita, >>. Muitos compiladores C escolhem qual turno certo executar, dependendo de qual tipo de inteiro está sendo deslocado; os inteiros geralmente assinados são deslocados usando o deslocamento aritmético, e inteiros sem sinal são deslocados usando o deslocamento lógico.

Então parece que depende do seu compilador. Também nesse artigo, observe que o deslocamento à esquerda é o mesmo para aritmética e lógica. Eu recomendaria fazer um teste simples com alguns números assinados e não assinados no caso de borda (alto conjunto de bits, é claro) e ver qual é o resultado em seu compilador. Eu também recomendaria evitar dependendo de ser um ou outro, uma vez que parece C não tem padrão, pelo menos, se é razoável e possível evitar essa dependência.


Answer #4

De acordo com a 2ª edição do K & R, os resultados são dependentes da implementação para os deslocamentos à direita dos valores assinados.

Wikipedia diz que o C / C ++ 'geralmente' implementa uma mudança aritmética nos valores assinados.

Basicamente, você precisa testar seu compilador ou não confiar nele. Minha ajuda VS2008 para o compilador MS C ++ atual diz que seu compilador faz uma mudança aritmética.


Answer #5

Deslocamento à esquerda <<

Isto é de alguma forma fácil e sempre que você usa o operador shift, é sempre uma operação bit-wise, então não podemos usá-lo com uma operação double e float. Sempre que saímos de um zero, ele é sempre adicionado ao bit menos significativo ( LSB ).

Mas no deslocamento à direita >> temos que seguir uma regra adicional e essa regra é chamada de "cópia de bit de sinal". Significado de "cópia de bit de sinal" é se o bit mais significativo ( MSB ) é definido depois de um desvio à direita novamente o MSB será definido se foi redefinido, em seguida, é novamente redefinido, significa que se o valor anterior foi zero depois de mudar novamente , o bit é zero se o bit anterior for um, depois do turno é novamente um. Esta regra não é aplicável para um turno esquerdo.

O exemplo mais importante no deslocamento à direita se você deslocar qualquer número negativo para o deslocamento à direita, depois de algum deslocamento, o valor finalmente chegará a zero e depois disso, se mudar este -1, qualquer número de vezes que o valor permanecerá igual. Por favor, verifique.


Answer #6

Em termos do tipo de mudança que você recebe, o importante é o tipo de valor que você está mudando. Uma fonte clássica de bugs é quando você muda um literal para, digamos, mascarar bits. Por exemplo, se você quiser soltar o bit mais à esquerda de um inteiro não assinado, poderá tentar isso como sua máscara:

~0 >> 1

Infelizmente, isso causará problemas porque a máscara terá todos os seus bits definidos porque o valor que está sendo alterado (~ 0) é assinado, portanto, uma mudança aritmética é executada. Em vez disso, você desejaria forçar uma mudança lógica ao declarar explicitamente o valor como não assinado, isto é, fazendo algo assim:

~0U >> 1;

Answer #7

Quando você faz - desloca para a esquerda em 1 você multiplica por 2 - desloca para a direita em 1 você divide por 2

 x = 5
 x >> 1
 x = 2 ( x=5/2)

 x = 5
 x << 1
 x = 10 (x=5*2)

Answer #8

gcc normalmente usa mudanças lógicas em variáveis ​​não assinadas e em deslocamentos esquerdos em variáveis ​​assinadas. O deslocamento à direita aritmético é o verdadeiramente importante porque ele assinará estender a variável.

gcc irá usar isto quando aplicável, como é provável que outros compiladores façam.





bit-shift