Eu tenho tentado aprender C no meu tempo livre, e outras linguagens (C #, Java etc.) têm o mesmo conceito (e geralmente os mesmos operadores) ...

O que eu estou querendo saber é, a nível central, o que faz-bit deslocando ( <<, >>, >>>) fazer, quais os problemas que ele pode ajudar a resolver, eo que gotchas espreitam ao redor da curva? Em outras palavras, um guia para iniciantes absolutos para mudar de bits em toda a sua bondade.

Os operadores de troca de bits fazem exatamente o que o nome indica. Eles trocam bits. Aqui está uma breve introdução (ou não tão breve) aos diferentes operadores de turno.

Os operadores

• >> é o operador aritmético (ou assinado) do deslocamento à direita.
• >>> é o operador de mudança à direita lógico (ou não assinado).
• << é o operador de turno esquerdo e atende às necessidades de turnos lógicos e aritméticos.

Todos estes operadores pode ser aplicada aos valores inteiros ( int, long, possivelmente, shorte byteou char). Em alguns idiomas, a aplicação dos operadores shift a qualquer tipo de dados menor que intredimensiona automaticamente o operando para ser um int.

Observe que <<<não é um operador, porque seria redundante.

Observe também que C e C ++ não fazem distinção entre os operadores de turno certo . Eles fornecem apenas o >>operador, e o comportamento de mudança à direita é a implementação definida para tipos assinados. O restante da resposta usa os operadores C # / Java.

(Em todas as implementações C e C ++ convencionais, incluindo GCC e Clang / LLVM, os >>tipos assinados são aritméticos. Alguns códigos assumem isso, mas não é algo que o padrão garante. Porém, não é indefinido ; o padrão exige implementações para defini-lo como um No entanto, as mudanças à esquerda de números com sinal negativo não são um comportamento indefinido (estouro de número inteiro assinado). Portanto, a menos que você precise de uma mudança aritmética à direita, geralmente é uma boa ideia fazer a troca de bits com tipos não assinados.)

Deslocamento para a esquerda (<<)

Os números inteiros são armazenados, na memória, como uma série de bits. Por exemplo, o número 6 armazenado como um de 32 bits intseria:

00000000 00000000 00000000 00000110

Mudar esse padrão de bit para a posição esquerda ( 6 << 1) resultaria no número 12:

00000000 00000000 00000000 00001100

Como você pode ver, os dígitos foram deslocados para a esquerda em uma posição e o último dígito à direita é preenchido com um zero. Você também pode observar que o deslocamento para a esquerda é equivalente à multiplicação por potências de 2. Portanto, 6 << 1é equivalente a 6 * 2e 6 << 3é equivalente a 6 * 8. Um bom compilador de otimização substituirá multiplicações por turnos quando possível.

Mudança não circular

Observe que estes não são turnos circulares. Deslocando esse valor para a esquerda em uma posição ( 3,758,096,384 << 1):

11100000 00000000 00000000 00000000

resulta em 3.221.225.472:

11000000 00000000 00000000 00000000

O dígito que é deslocado "no final" é perdido. Não envolve.

Deslocamento lógico para a direita (>>>)

Um deslocamento lógico para a direita é o inverso para o deslocamento para a esquerda. Em vez de mover bits para a esquerda, eles simplesmente se movem para a direita. Por exemplo, mudando o número 12:

00000000 00000000 00000000 00001100

à direita em uma posição ( 12 >>> 1) retornará nosso 6 original:

00000000 00000000 00000000 00000110

Portanto, vemos que mudar para a direita é equivalente à divisão por potências de 2.

Pedaços perdidos se foram

No entanto, uma mudança não pode recuperar bits "perdidos". Por exemplo, se mudarmos esse padrão:

00111000 00000000 00000000 00000110

para a esquerda 4 posições ( 939,524,102 << 4), temos 2.147.483.744:

10000000 00000000 00000000 01100000

e, em seguida, mudando de volta ( (939,524,102 << 4) >>> 4), obtemos 134.217.734:

00001000 00000000 00000000 00000110

Não podemos recuperar nosso valor original depois que perdemos os bits.

Desvio aritmético para a direita (>>)

O deslocamento aritmético para a direita é exatamente igual ao deslocamento lógico para a direita, exceto que, em vez de preencher com zero, ele almofada com o bit mais significativo. Isso ocorre porque o bit mais significativo é o bit de sinal ou o bit que distingue números positivos e negativos. Ao preencher com o bit mais significativo, a mudança aritmética para a direita preserva os sinais.

Por exemplo, se interpretarmos esse padrão de bits como um número negativo:

10000000 00000000 00000000 01100000

nós temos o número -2.147.483.552. Mudar isso para as 4 posições corretas com o deslocamento aritmético (-2.147.483.552 >> 4) nos daria:

11111000 00000000 00000000 00000110

ou o número -134.217.722.

Portanto, vemos que preservamos o sinal de nossos números negativos, usando o deslocamento aritmético para a direita, em vez do deslocamento lógico para a direita. E mais uma vez, vemos que estamos realizando a divisão por potências de 2.

Digamos que temos um único byte:

0110110

A aplicação de um único deslocamento de bits à esquerda nos leva a:

1101100

O zero mais à esquerda foi deslocado para fora do byte e um novo zero foi anexado à extremidade direita do byte.

Os bits não rolam; eles são descartados. Isso significa que, se você saiu do turno 1101100 e depois do turno à direita, não obterá o mesmo resultado.

Deslocamento para a esquerda por N é equivalente a multiplicar por 2 ^N .

Deslocar para a direita por N é (se você estiver usando o complemento de um ) é o equivalente a dividir por 2 ^N e arredondar para zero.

O deslocamento de bits pode ser usado para multiplicação e divisão incrivelmente rápidas, desde que você esteja trabalhando com uma potência de 2. Quase todas as rotinas gráficas de baixo nível usam deslocamento de bits.

Por exemplo, no passado, usamos o modo 13h (320x200 256 cores) para jogos. No modo 13h, a memória de vídeo foi organizada sequencialmente por pixel. Para calcular a localização de um pixel, você usaria a seguinte matemática:

memoryOffset = (row * 320) + column

Agora, naquele dia e idade, a velocidade era crítica, então usamos turnos de bits para fazer essa operação.

No entanto, 320 não é um poder de dois, então, para contornar isso, precisamos descobrir o que é um poder de dois que somados faz 320:

(row * 320) = (row * 256) + (row * 64)

Agora podemos converter isso em turnos à esquerda:

(row * 320) = (row << 8) + (row << 6)

Para um resultado final de:

memoryOffset = ((row << 8) + (row << 6)) + column

Agora temos o mesmo deslocamento de antes, exceto que, em vez de uma operação cara de multiplicação, usamos os dois turnos de bits ... em x86 seria algo parecido com isto (note, já faz uma eternidade desde que eu fiz a montagem (nota do editor: corrigida alguns erros e adicionou um exemplo de 32 bits)):

mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]

; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov

Total: 28 ciclos em qualquer CPU antiga que tivesse esses tempos.

Vrs

mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6;  2
shl di, 8;  2
add di, ax; 2    (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]

12 ciclos na mesma CPU antiga.

Sim, trabalharíamos muito para reduzir 16 ciclos de CPU.

No modo de 32 ou 64 bits, ambas as versões ficam muito mais curtas e rápidas. As CPUs modernas de execução fora de ordem, como o Intel Skylake (consulte http://agner.org/optimize/ ), têm uma multiplicação muito rápida de hardware (baixa latência e alta taxa de transferência); portanto, o ganho é muito menor. A família AMD Bulldozer é um pouco mais lenta, especialmente para a multiplicação de 64 bits. Nos processadores Intel e AMD Ryzen, duas mudanças são uma latência ligeiramente menor, mas mais instruções do que uma multiplicação (que pode levar a uma taxa de transferência menor):

imul edi, [row], 320    ; 3 cycle latency from [row] being ready
add  edi, [column]      ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column],  in 4 cycles from [row] being ready.

vs.

mov edi, [row]
shl edi, 6               ; row*64.   1 cycle latency
lea edi, [edi + edi*4]   ; row*(64 + 64*4).  1 cycle latency
add edi, [column]        ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column],  in 3 cycles from [row] being ready.

Os compiladores farão isso por você: Veja como o GCC, Clang e Microsoft Visual C ++ usam shift + lea ao otimizarreturn 320*row + col; .

O mais interessante a ser observado aqui é que o x86 possui uma instrução shift-and-add ( LEA) que pode fazer pequenos turnos à esquerda e adicionar ao mesmo tempo, com o desempenho como uma addinstrução. O ARM é ainda mais poderoso: um operando de qualquer instrução pode ser deslocado para a esquerda ou para a direita gratuitamente. Portanto, o dimensionamento por uma constante em tempo de compilação que é conhecida como uma potência de 2 pode ser ainda mais eficiente do que uma multiplicação.

OK, nos dias modernos ... algo mais útil agora seria usar o deslocamento de bits para armazenar dois valores de 8 bits em um número inteiro de 16 bits. Por exemplo, em C #:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

No C ++, os compiladores devem fazer isso por você se você usou um structcom dois membros de 8 bits, mas na prática eles nem sempre.

Operações bit a bit, incluindo troca de bits, são fundamentais para hardware de baixo nível ou programação incorporada. Se você ler uma especificação para um dispositivo ou até mesmo alguns formatos de arquivos binários, verá bytes, palavras e dwords divididos em campos de bits alinhados que não são de bytes, que contêm vários valores de interesse. O acesso a esses campos de bits para leitura / gravação é o uso mais comum.

Um exemplo real simples de programação gráfica é que um pixel de 16 bits é representado da seguinte maneira:

  bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1  | 0 |
      |       Blue        |         Green         |       Red          |

Para obter o valor verde, você faria o seguinte:

 #define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5

 // Read green
 uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Explicação

Para obter o valor de ONLY verde, que começa no deslocamento 5 e termina em 10 (ou seja, 6 bits de comprimento), você precisa usar uma máscara (de bits) que, quando aplicada contra todo o pixel de 16 bits, produzirá apenas os bits em que estamos interessados.

#define GREEN_MASK  0x7E0

A máscara apropriada é 0x7E0, que em binário é 0000011111100000 (que é 2016 em decimal).

uint16_t green = (pixel & GREEN_MASK) ...;

Para aplicar uma máscara, use o operador AND (&).

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Depois de aplicar a máscara, você terá um número de 16 bits, que na verdade é apenas um número de 11 bits, já que o MSB está no 11º bit. O verde tem, na verdade, apenas 6 bits de comprimento, então precisamos reduzi-lo usando o deslocamento à direita (11 - 6 = 5), daí o uso de 5 como deslocamento ( #define GREEN_OFFSET 5).

Também é comum o uso de deslocamento de bits para multiplicação e divisão rápidas por potências de 2:

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;

Mascaramento e mudança de bits

A troca de bits é frequentemente usada na programação gráfica de baixo nível. Por exemplo, um determinado valor de cor de pixel codificado em uma palavra de 32 bits.

 Pixel-Color Value in Hex:    B9B9B900
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Para uma melhor compreensão, o mesmo valor binário rotulado com quais seções representam qual parte da cor.

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Digamos, por exemplo, que queremos obter o valor verde da cor desse pixel. Podemos facilmente obter esse valor mascarando e mudando .

Nossa máscara:

                  Red      Green      Blue      Alpha
 color :        10111001  10111001  10111001  00000000
 green_mask  :  00000000  11111111  00000000  00000000

 masked_color = color & green_mask

 masked_color:  00000000  10111001  00000000  00000000

O &operador lógico garante que apenas os valores em que a máscara seja 1 sejam mantidos. A última coisa que precisamos fazer agora é obter o valor inteiro correto deslocando todos esses bits para a direita em 16 lugares (deslocamento lógico para a direita) .

 green_value = masked_color >>> 16

E pronto, temos o número inteiro representando a quantidade de verde na cor do pixel:

 Pixels-Green Value in Hex:     000000B9
 Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001
 Pixels-Green Value in Decimal: 185

Isto é frequentemente usado para a codificação ou decodificação de formatos de imagem, como jpg, png, etc.

Um problema é que o seguinte depende da implementação (de acordo com o padrão ANSI):

char x = -1;
x >> 1;

x pode agora ser 127 (01111111) ou ainda -1 (11111111).

Na prática, geralmente é o último.

Estou escrevendo apenas dicas e truques. Pode ser útil em testes e exames.

1. n = n*2: n = n<<1
2. n = n/2: n = n>>1
3. Verificando se n é a potência de 2 (1,2,4,8, ...): verifique !(n & (n-1))
4. Obtendo x ^th bit de n:n |= (1 << x)
5. Verificando se x é par ou ímpar: x&1 == 0(par)
6. Alternar a n ^th pouco de x:x ^ (1<<n)

Observe que na implementação Java, o número de bits a serem alterados é modificado pelo tamanho da fonte.

Por exemplo:

(long) 4 >> 65

é igual a 2. Você pode esperar que mudar os bits para a direita 65 vezes zere tudo, mas na verdade é o equivalente a:

(long) 4 >> (65 % 64)

Isso vale para <<, >> e >>>. Eu não tentei em outros idiomas.

Algumas operações / manipulações de bits úteis em Python.

Eu implementei a resposta de Ravi Prakash em Python.

# Basic bit operations
# Integer to binary
print(bin(10))

# Binary to integer
print(int('1010', 2))

# Multiplying x with 2 .... x**2 == x << 1
print(200 << 1)

# Dividing x with 2 .... x/2 == x >> 1
print(200 >> 1)

# Modulo x with 2 .... x % 2 == x & 1
if 20 & 1 == 0:
    print("20 is a even number")

# Check if n is power of 2: check !(n & (n-1))
print(not(33 & (33-1)))

# Getting xth bit of n: (n >> x) & 1
print((10 >> 2) & 1) # Bin of 10 == 1010 and second bit is 0

# Toggle nth bit of x : x^(1 << n)
# take bin(10) == 1010 and toggling second bit in bin(10) we get 1110 === bin(14)
print(10^(1 << 2))

Esteja ciente de que apenas a versão de 32 bits do PHP está disponível na plataforma Windows.

Então, se você, por exemplo, mudar << ou >> mais do que 31 bits, os resultados serão inesperados. Normalmente, o número original em vez de zeros será retornado, e pode ser um bug muito complicado.

Obviamente, se você usa a versão de 64 bits do PHP (Unix), deve evitar mudar mais de 63 bits. No entanto, por exemplo, o MySQL usa o BIGINT de 64 bits, portanto não deve haver nenhum problema de compatibilidade.

ATUALIZAÇÃO: No PHP 7 Windows, as compilações PHP finalmente podem usar números inteiros de 64 bits: O tamanho de um número inteiro depende da plataforma, embora um valor máximo de cerca de dois bilhões seja o valor usual (que é assinado em 32 bits). As plataformas de 64 bits geralmente têm um valor máximo de cerca de 9E18, exceto no Windows anterior ao PHP 7, onde sempre eram 32 bits.