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

Respostas:

97

De acordo com a K&R 2nd edition, os resultados dependem da implementação para mudanças corretas dos valores assinados.

A Wikipedia diz que 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 do VS2008 para o atual compilador MS C ++ diz que o compilador faz uma alteração aritmética.

Ronnie
fonte
141

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

(Como pano de fundo para os leitores não familiarizados com a diferença, um deslocamento "lógico" para a direita em 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 se torna importante ao lidar com números negativos.)

Ao mudar um valor não assinado, o operador >> em C é uma mudança lógica. Ao mudar um valor assinado, 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);
Greg Hewgill
fonte
57
Tão perto, Greg. Sua explicação é quase perfeita, mas mudar uma expressão do tipo assinado e do valor negativo é definido pela implementação. Veja ISO / IEC 9899: 1999, Seção 6.5.7.
Robᵩ
12
@ Rob: Na verdade, para o turno esquerdo e número negativo assinado, o comportamento é indefinido.
precisa saber é o seguinte
5
Na verdade, o deslocamento para a esquerda também resulta em um comportamento indefinido para valores assinados positivos se o valor matemático resultante (que não é limitado no tamanho do bit) não puder ser representado como um valor positivo nesse tipo assinado. A linha inferior é que você deve agir com cuidado ao mudar à direita um valor assinado.
Michael Burr
3
@ supercat: Eu realmente não sei. No entanto, eu sei que existem casos documentados em que o código que tem um comportamento indefinido faz com que um compilador faça coisas muito pouco intuitivas (geralmente devido à otimização agressiva - por exemplo, consulte o bug antigo do ponteiro nulo do driver Linux TUN / TAP: lwn.net / Artigos / 342330 ). A menos que eu precise de preenchimento de sinal no turno certo (o que eu percebo ser um comportamento definido pela implementação), geralmente tento executar meus turnos de bits usando valores não assinados, mesmo que isso signifique usar conversões para chegar lá.
Michael Burr
2
@ MichaelBurr: Eu sei que os compiladores hipermodernos usam o fato de que o comportamento não foi definido pelo padrão C (apesar de ter sido definido em 99% das implementações ) como uma justificativa para ativar programas cujo comportamento teria sido totalmente definido em todos plataformas nas quais se espera que funcionem, em conjuntos inúteis de instruções da máquina sem nenhum comportamento útil. Eu admito, no entanto, (sarcasmo ativado), estou intrigado com o motivo pelo qual os autores do compilador perderam a maior possibilidade de otimização: omitir qualquer parte de um programa que, se atingido, resultaria em
aninhamento de
51

TL; DR

Considere ie nsejam os operandos esquerdo e direito, respectivamente, de um operador de turno; o tipo de i, após a promoção inteira, seja T. Assumindo nestar dentro [0, sizeof(i) * CHAR_BIT)- indefinido de outra forma - temos os seguintes 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 deslocamento aritmético
‡ indefinido se o valor ultrapassar o tipo de resultado T; tipo promovido de i


Mudança

Primeiro, a diferença entre mudanças lógicas e aritméticas do ponto de vista matemático, sem se preocupar com o tamanho do tipo de dados. Os turnos lógicos sempre preenchem os bits descartados com zeros, enquanto o turno aritmético os preenche apenas com o turno esquerdo, mas, no turno direito, ele copia o MSB preservando o sinal do operando (assumindo o complemento de dois para codificar valores negativos).

Em outras palavras, a mudança lógica considera o operando alterado como apenas um fluxo de bits e os move, sem se preocupar com o sinal do valor resultante. O deslocamento aritmético o vê como um número (assinado) e preserva o sinal à medida que os turnos são feitos.

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

Um deslocamento aritmético à direita de um número X por n é equivalente à divisão inteira de X por 2 n SOMENTE se X for não negativo! Divisão inteira não é senão divisão matemática e arredondada para 0 ( trunc ).

Para números negativos, representados pela codificação do complemento de dois, deslocar para a direita por n bits tem o efeito de dividi-lo matematicamente por 2 n e arredondar para −∞ ( piso ); portanto, o deslocamento à 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 ÷é a divisão matemática, /é a divisão inteira. Vejamos 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 aritmético para a direita]

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

-37 ÷ 2 = -18,5

-37 / 2 = -18 (arredondando 18,5 para 0) = 11101110) 2 [NÃO é o resultado do deslocamento aritmético para a direita]

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

Como Guy Steele apontou , essa discrepância levou a erros em mais de um compilador . 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 forma e o deslocamento à direita é feito por divisão inteira.

Portanto, lógico e aritmético são equivalentes no deslocamento para a esquerda e para valores não negativos no deslocamento para a direita; é na mudança correta de valores negativos que eles diferem.

Tipos de operando e resultado

Norma C99 §6.5.7 :

Cada um dos operandos deve ter tipos inteiros.

As promoções de números inteiros 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 será indefinido.

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

No trecho acima, ambos os operandos se tornam int(devido à promoção de número inteiro); se E2foi negativo ou E2 ≥ sizeof(int) * CHAR_BITentão a operação é indefinida. Isso ocorre porque o deslocamento de mais do que os bits disponíveis certamente transbordará. Se tivesse Rsido declarado como short, o intresultado da operação de turno seria implicitamente convertido em short; uma conversão restritiva, que pode levar ao comportamento definido pela implementação se o valor não for representável no tipo de destino.

Desvio à esquerda

O resultado de E1 << E2 são as posições de bit E2 com deslocamento à esquerda E1; bits desocupados 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, esse será o valor resultante; caso contrário, o comportamento é indefinido.

Como os desvios à esquerda são os mesmos para ambos, os bits desocupados são simplesmente preenchidos com zeros. Ele então afirma que, para os tipos não assinados e assinados, é uma mudança aritmética. Estou interpretando isso como uma mudança aritmética, pois as mudanças lógicas não se preocupam com o valor representado pelos bits, mas apenas como um fluxo de bits; mas o padrão fala não 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 após a aplicação da promoção integral e não o tipo de destino (a variável que manterá o resultado). O valor resultante é convertido implicitamente no tipo de destino; se não for representável nesse tipo, a conversão será definida pela implementação (C99 §6.3.1.3 / 3).

Se E1 for um tipo assinado com um valor negativo, o comportamento do deslocamento para a esquerda é indefinido. Esse é um caminho fácil para um comportamento indefinido que pode ser facilmente esquecido.

Deslocamento para a direita

O resultado de E1 >> E2 são as posições de bits E2 deslocadas à direita. Se E1 tiver um tipo não assinado ou E1 tiver um tipo assinado e um valor não negativo, o valor do resultado será parte integrante do quociente E1 / 2 E2 . Se E1 tiver um tipo assinado e um valor negativo, o valor resultante será definido pela implementação.

O deslocamento certo para valores não negativos não assinados e assinados é bastante direto; os bits vagos 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 GCC e Visual C ++ implementam a mudança à direita como mudança aritmética, preservando o bit de sinal.

Conclusão

Diferente do Java, que possui um operador especial >>>para deslocamento lógico além do usual >>e <<, C e C ++ têm apenas deslocamento aritmético com algumas áreas deixadas indefinidas e definidas pela implementação. A razão pela qual eu os considero aritméticos é devido à formulação padrão da operação matematicamente, em vez de tratar o operando alterado como um fluxo de bits; talvez essa seja a razão pela qual deixa essas áreas sem definição de implementação, em vez de apenas definir todos os casos como mudanças lógicas.

legends2k
fonte
1
Boa resposta. No que diz respeito ao arredondamento (na seção intitulada Deslocamento ) - o deslocamento à direita arredonda para -Infnúmeros negativos e positivos. Arredondar para 0 de um número positivo é um caso particular de arredondamento para -Inf. Ao truncar, você sempre descarta valores ponderados positivamente e, portanto, subtrai do resultado preciso.
ysap
1
@ syap Sim, boa observação. Basicamente, arredondar para 0 para números positivos é um caso especial da rodada mais geral para −∞; isso pode ser visto na tabela, onde tanto os números positivos quanto os negativos foram anotados como redondos para −∞.
Legends2k 11/0318
17

Em termos do tipo de turno que você recebe, o importante é o tipo de valor que você está mudando. Uma fonte clássica de erros é quando você muda um literal para, por exemplo, mascarar os bits. Por exemplo, se você deseja soltar o bit mais à esquerda de um número inteiro não assinado, tente isso como sua máscara:

~0 >> 1

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

~0U >> 1;
usuario
fonte
16

Aqui estão as funções para garantir o deslocamento lógico à direita e o deslocamento aritmético à direita de um int em C:

int logicalRightShift(int x, int n) {
    return (unsigned)x >> n;
}
int arithmeticRightShift(int x, int n) {
    if (x < 0 && n > 0)
        return x >> n | ~(~0U >> n);
    else
        return x >> n;
}
John Scipione
fonte
7

Quando você faz - desvio à esquerda por 1, você multiplica por 2 - desvio à direita por 1, divide por 2

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

 x = 5
 x << 1
 x = 10 (x=5*2)
Srikant Patnaik
fonte
Em x >> aex << a se a condição for a> 0, então a resposta é x = x / 2 ^ a, x = x * 2 ^ a respectivamente, então Qual seria a resposta se a <0?
JAVA
@sunny: um não deve ser menor do que 0. É um comportamento indefinido em C.
Jeremy
4

Bem, procurei na wikipedia e eles têm o seguinte a dizer:

C, no entanto, possui apenas um operador de turno direito, >>. Muitos compiladores C escolhem qual turno certo executar, dependendo do tipo de número inteiro que está sendo alterado; números inteiros frequentemente assinados são deslocados usando o deslocamento aritmético e números inteiros não assinados são deslocados usando o deslocamento lógico.

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

Mike Stone
fonte
Embora a maioria dos compiladores C costumava ter um desvio à esquerda aritmético para valores assinados, esse comportamento útil parece ter sido preterido. A filosofia atual do compilador parece assumir que o desempenho de um turno à esquerda em uma variável autoriza um compilador a assumir que a variável deve ser não negativa e, portanto, omitir qualquer código em outro lugar que seria necessário para o comportamento correto se a variável fosse negativa .
supercat
0

Desvio à esquerda <<

De alguma forma, isso é fácil e sempre que você usa o operador de turno, é sempre uma operação pouco a pouco, portanto não podemos usá-lo com uma operação double e float. Sempre que deixamos o deslocamento um zero, ele sempre é adicionado ao bit menos significativo ( LSB).

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

O exemplo mais importante no deslocamento para a direita, se você mudar qualquer número negativo para o deslocamento para a direita, depois de algumas mudanças, o valor finalmente chegará a zero e, depois disso, se a mudança for -1, qualquer número de vezes que o valor permanecerá o mesmo. Por favor, verifique.

asifaftab87
fonte
0

normalmente usará turnos lógicos em variáveis ​​não assinadas e para turnos à esquerda em variáveis ​​assinadas. O deslocamento aritmético para a direita é o verdadeiramente importante, porque irá estender a variável.

usará isso quando aplicável, como outros compiladores provavelmente o farão.

Cristián Romo
fonte
-1

O GCC faz

  1. for -ve -> Mudança aritmética

  2. Para + ve -> Mudança Lógica

Alok Prasad
fonte
-7

De acordo com muitos compiladores:

  1. << é um desvio à esquerda aritmético ou um desvio à esquerda bit a bit.
  2. >> é um deslocamento aritmético para a direita ou deslocamento para a direita em bits.
srinath
fonte
3
"Turno direito aritmético" e "turno direito bit a bit" são diferentes. Esse é o ponto da questão. A pergunta era " >>Aritmética ou bit a bit (lógica)?" Você respondeu " >>é aritmético ou bit a bit". Isso não responde à pergunta.
Wchargin
Não, <<e >>os operadores são lógicos, não aritmética
shjeff