O que são operadores de troca bit a bit (troca por bit) e como eles funcionam?

1382

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.

John Rudy
fonte
2
Os casos funcionais ou não funcionais nos quais você usaria o deslocamento de bits no 3GL são poucos.
Troy DeMonbreun 26/09/08
16
Depois de ler essas respostas você pode querer olhar para estes links: graphics.stanford.edu/~seander/bithacks.html & jjj.de/bitwizardry/bitwizardrypage.html
garras
1
É importante observar que a troca de bits é extremamente fácil e rápida para os computadores. Ao encontrar maneiras de usar a troca de bits em seu programa, você pode reduzir bastante o uso de memória e os tempos de execução.
precisa saber é o seguinte
@ Haytman: Mas observe que bons compiladores já conhecem muitos desses truques e geralmente são melhores em reconhecer onde faz sentido.
Sebastian Mach

Respostas:

1713

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.

Derek Park
fonte
304
A resposta deve deixar mais claro que esta é uma resposta específica de Java. Não existe >>> operador em C / C ++ ou C #, e se ou não >> propaga o sinal é definido pela implementação em C / C ++ (a maior pegadinha potencial)
Michael Burr
56
A resposta está totalmente incorreta no contexto da linguagem C. Não há divisão significativa em mudanças "aritméticas" e "lógicas" em C. Em C, as mudanças funcionam conforme o esperado em valores não assinados e valores positivos assinados - eles apenas mudam os bits. Em valores negativos, o deslocamento à direita é definido pela implementação (ou seja, nada pode ser dito sobre o que faz em geral) e o deslocamento à esquerda é simplesmente proibido - produz comportamento indefinido.
AnT
10
Audrey, certamente há uma diferença entre a aritmética e a mudança lógica para a direita. C simplesmente deixa a implementação de escolha definida. E o desvio para a esquerda em valores negativos definitivamente não é proibido. Desloque 0xff000000 para a esquerda um pouco e você obterá 0xfe000000.
Derek Park
16
A good optimizing compiler will substitute shifts for multiplications when possible. O que? Os turnos de bits são ordens de magnitude mais rápidas quando se trata das operações de baixo nível de uma CPU, um bom compilador de otimização faria exatamente o oposto, ou seja, transformar multiplicações comuns por potências de dois em turnos de bits.
Mahn
55
@ Mahn, você está lendo isso da minha intenção. Substituir Y por X significa substituir X por Y. Y é o substituto de X. Portanto, o deslocamento é o substituto da multiplicação.
Derek Park
209

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.

FlySwat
fonte
8
Expandindo isso, nos processadores Intel (e muitos outros) é mais rápido fazer isso: int c, d; c = d << 2; Do que isso: c = 4 * d; Às vezes, até "c = d << 2 + d << 1" é mais rápido que "c = 6 * d" !! Eu usei esses truques extensivamente para funções gráficas na era DOS, eu não acho que eles são tão mais útil ...
Joe Pineda
5
@ James: não exatamente, hoje em dia é o firmware da placa de vídeo que inclui um código como esse, a ser executado pela GPU e não pela CPU. Então, teoricamente, você não precisa implementar um código como este (ou como função de magia negra inversa raiz do Carmack) para funções gráficas :-)
Joe Pineda
3
@JoePineda @james Os escritores do compilador definitivamente os estão usando. Se você escrever c=4*d, terá uma mudança. Se você escrever k = (n<0)isso também pode ser feito com turnos: k = (n>>31)&1para evitar um galho. Resumindo, esse aprimoramento na inteligência dos compiladores significa que agora não é necessário usar esses truques no código C, e eles comprometem a legibilidade e a portabilidade. Ainda é muito bom conhecê-los se você estiver escrevendo, por exemplo, código vetorial SSE; ou qualquer situação em que você precise rápido e há um truque que o compilador não está usando (por exemplo, código da GPU).
Greggo
2
Outro bom exemplo: algo muito comum é o if(x >= 1 && x <= 9)que pode ser feito, pois if( (unsigned)(x-1) <=(unsigned)(9-1)) alterar dois testes condicionais para um pode ser uma grande vantagem de velocidade; especialmente quando permite execução predicada em vez de ramificações. Eu usei isso por anos (quando justificado) até notar há 10 anos que os compiladores começaram a fazer essa transformação no otimizador e parei. Ainda é bom saber, pois existem situações semelhantes em que o compilador não pode fazer a transformação para você. Ou se você estiver trabalhando em um compilador.
Greggo
3
Existe uma razão para o seu "byte" ter apenas 7 bits?
Mason Watmough
104

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;
robottobor
fonte
1
0x7e0 é o mesmo que 11111100000, que é 2016 em decimal.
Saheed
50

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.

Basti Funck
fonte
Não é mais fácil converter o original, digamos, 32 bits cl_uint, como algo como cl_uchar4 e acessar o byte desejado diretamente como * .s2?
David H Parry
27

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.

AShelly
fonte
4
Se bem me lembro, o padrão ANSI C diz explicitamente que isso depende da implementação; portanto, você precisa verificar a documentação do seu compilador para ver como ele é implementado, se você quiser mudar o número inteiro assinado no seu código.
Joe Pineda
Sim, eu só queria enfatizar que o próprio padrão ANSI diz isso, não é um caso em que os fornecedores simplesmente não estão seguindo o padrão ou que o padrão não diz nada sobre esse caso específico.
Joe Pineda
22

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)
Ravi Prakash
fonte
Deve haver um pouco mais do que você sabe até agora?
ryyker
@ryyker Adicionei mais alguns. Vou tentar manter atualizá-lo :)
Ravi Prakash
X e n 0 são indexados?
Reggaeguitar
Anúncio 5: e se for um número negativo?
Peter Mortensen
então, podemos concluir que 2 em binário é 10 em decimal? e deslocamento de bits é como adicionar ou subtrair mais um número atrás de outro número em decimal?
Willy satrio nugroho 18/01
8

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.

Patrick Monkelban
fonte
Huh, interessante! Em C, esse é um comportamento tecnicamente indefinido . gcc 5.4.0dá um aviso, mas dá 25 >> 65; também.
precisa saber é o seguinte
2

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))
Peter Mortensen
fonte
-3

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.

lukyer
fonte