Operação bit a bit - Bitwise operation

Na programação de computadores , uma operação bit a bit opera em uma sequência de bits , uma matriz de bits ou um numeral binário (considerado como uma sequência de bits) no nível de seus bits individuais . É uma ação rápida e simples, básica para as operações aritméticas de nível superior e suportada diretamente pelo processador . A maioria das operações bit a bit é apresentada como instruções de dois operandos, em que o resultado substitui um dos operandos de entrada.

Em processadores simples de baixo custo, normalmente, as operações bit a bit são substancialmente mais rápidas do que a divisão, várias vezes mais rápidas do que a multiplicação e, às vezes, significativamente mais rápidas do que a adição. Enquanto os processadores modernos geralmente executam adição e multiplicação tão rápido quanto as operações bit a bit devido a seus pipelines de instrução mais longos e outras opções de design arquitetônico , as operações bit a bit normalmente usam menos energia devido ao uso reduzido de recursos.

Operadores bit a bit

Nas explicações abaixo, qualquer indicação da posição de um bit é contada do lado direito (menos significativo), avançando para a esquerda. Por exemplo, o valor binário 0001 (decimal 1) tem zeros em todas as posições, exceto o primeiro (ou seja, o mais à direita).

NÃO

O NOT bit a bit , ou complemento , é uma operação unária que realiza negação lógica em cada bit, formando o complemento de uns do valor binário dado. Os bits que são 0 tornam-se 1 e os que são 1 tornam-se 0. Por exemplo:

NOT 0111  (decimal 7)
  = 1000  (decimal 8)
NOT 10101011  (decimal 171)
  = 01010100  (decimal 84)

O complemento bit a bit é igual ao complemento de dois do valor menos um. Se a aritmética do complemento de dois for usada, então NOT x = -x − 1.

Para inteiros sem sinal , o complemento bit a bit de um número é o "reflexo espelhado" do número na metade do intervalo do inteiro sem sinal. Por exemplo, para inteiros não assinados de 8 bits NOT x = 255 - x, que podem ser visualizados em um gráfico como uma linha descendente que efetivamente "vira" um intervalo crescente de 0 a 255, para um intervalo decrescente de 255 a 0. Um exemplo simples, mas ilustrativo, usa é inverter uma imagem em tons de cinza onde cada pixel é armazenado como um inteiro sem sinal.

E

E bit a bit de inteiros de 4 bits

Um AND bit a bit é uma operação binária que recebe duas representações binárias de comprimento igual e executa a operação AND lógica em cada par dos bits correspondentes, o que é equivalente a multiplicá-los. Assim, se ambos os bits na posição comparada forem 1, o bit na representação binária resultante será 1 (1 × 1 = 1); caso contrário, o resultado é 0 (1 × 0 = 0 e 0 × 0 = 0). Por exemplo:

    0101 (decimal 5)
AND 0011 (decimal 3)
  = 0001 (decimal 1)

A operação pode ser usada para determinar se um determinado bit está definido (1) ou limpo (0). Por exemplo, dado um padrão de bits 0011 (decimal 3), para determinar se o segundo bit está definido, usamos um AND bit a bit com um padrão de bits contendo 1 apenas no segundo bit:

    0011 (decimal 3)
AND 0010 (decimal 2)
  = 0010 (decimal 2)

Como o resultado 0010 é diferente de zero, sabemos que o segundo bit do padrão original foi definido. Isso geralmente é chamado de mascaramento de bits . (Por analogia, o uso de fita adesiva cobre, ou mascara , partes que não devem ser alteradas ou partes que não são de interesse. Nesse caso, os valores 0 mascaram os bits que não são de interesse.)

O bit a bit AND pode ser usado para limpar os bits selecionados (ou sinalizadores ) de um registro no qual cada bit representa um estado booleano individual . Essa técnica é uma maneira eficiente de armazenar vários valores booleanos usando o mínimo de memória possível.

Por exemplo, 0110 (decimal 6) pode ser considerado um conjunto de quatro sinalizadores, em que o primeiro e o quarto sinalizadores são claros (0) e o segundo e o terceiro sinalizadores são definidos (1). O terceiro sinalizador pode ser limpo usando um AND bit a bit com o padrão que tem um zero apenas no terceiro bit:

    0110 (decimal 6)
AND 1011 (decimal 11)
  = 0010 (decimal 2)

Por causa dessa propriedade, torna-se fácil verificar a paridade de um número binário verificando o valor do bit de menor valor. Usando o exemplo acima:

    0110 (decimal 6)
AND 0001 (decimal 1)
  = 0000 (decimal 0)

Como 6 E 1 é zero, 6 é divisível por dois e, portanto, par.

OU

OR bit a bit de inteiros de 4 bits

Um bit a bit OR é uma operação binária que usa dois padrões de bits de igual comprimento e executa a operação lógica de OR inclusiva em cada par de bits correspondentes. O resultado em cada posição é 0 se ambos os bits forem 0, enquanto, caso contrário, o resultado será 1. Por exemplo:

   0101 (decimal 5)
OR 0011 (decimal 3)
 = 0111 (decimal 7)

O bit a bit OR pode ser usado para definir como 1 os bits selecionados do registro descrito acima. Por exemplo, o quarto bit de 0010 (decimal 2) pode ser definido executando um bit a bit OR com o padrão com apenas o quarto bit definido:

   0010 (decimal 2)
OR 1000 (decimal 8)
 = 1010 (decimal 10)

XOR

XOR bit a bit de inteiros de 4 bits

Um XOR bit a bit é uma operação binária que usa dois padrões de bits de comprimento igual e executa a operação OR exclusiva lógica em cada par de bits correspondentes. O resultado em cada posição é 1 se apenas um dos bits for 1, mas será 0 se ambos forem 0 ou ambos forem 1. Neste realizamos a comparação de dois bits, sendo 1 se os dois bits forem diferentes, e 0 se eles são os mesmos. Por exemplo:

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)

O XOR bit a bit pode ser usado para inverter os bits selecionados em um registro (também chamado de alternar ou inverter). Qualquer bit pode ser alternado por XOR com 1. Por exemplo, dado o padrão de bits 0010 (decimal 2), o segundo e o quarto bits podem ser alternados por um XOR bit a bit com um padrão de bits contendo 1 na segunda e na quarta posições:

    0010 (decimal 2)
XOR 1010 (decimal 10)
  = 1000 (decimal 8)

Esta técnica pode ser usada para manipular padrões de bits que representam conjuntos de estados booleanos.

Os programadores de linguagem assembly e compiladores de otimização às vezes usam o XOR como um atalho para definir o valor de um registro como zero. Executar XOR em um valor em relação a si mesmo sempre resulta em zero, e em muitas arquiteturas esta operação requer menos ciclos de clock e memória do que carregar um valor zero e salvá-lo no registrador.

Se o conjunto de cadeias de bits de comprimento fixo n (isto é , palavras de máquina ) é pensado como um espaço vetorial n- dimensional sobre o campo , então a adição de vetor corresponde ao XOR bit a bit.

Equivalentes matemáticos

Supondo que , para os inteiros não negativos, as operações bit a bit podem ser escritas da seguinte forma:

Tabela verdade para todos os operadores lógicos binários

Existem 16 funções de verdade possíveis de duas variáveis ​​binárias ; isso define uma tabela verdade .

Aqui estão as operações equivalentes bit a bit de dois bits P e Q:

p q F 0 NOR 1 Xq 2 ¬p 3 4 ¬q 5 XOR 6 NAND 7 E 8 XNOR 9 q 10 Se / então 11 p 12 Então / se 13 OU 14 T 15
1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Equivalentes bit a bit
0 NÃO
(p OU q)
(NÃO p)
E q
NÃO
p
p AND
(NÃO q)
NÃO
q
p XOR q NÃO
(p AND q)
p AND q NÃO
(p XOR q)
q (NÃO p)
OU q
p p OU
(NÃO q)
p OR q 1

Mudanças de bits

Os deslocamentos de bits às vezes são considerados operações bit a bit, porque tratam um valor como uma série de bits em vez de uma quantidade numérica. Nessas operações, os dígitos são movidos, ou deslocados , para a esquerda ou direita. Os registros em um processador de computador têm uma largura fixa, portanto, alguns bits serão "deslocados" do registro em uma extremidade, enquanto o mesmo número de bits será "transferido" na outra extremidade; as diferenças entre os operadores de deslocamento de bits residem em como eles determinam os valores dos bits deslocados.

Endereçamento de bits

Se a largura do registro (freqüentemente 32 ou mesmo 64) for maior que o número de bits (geralmente 8) da menor unidade endereçável (elemento atômico), freqüentemente chamado de byte, as operações de deslocamento induzem um esquema de endereçamento dos bytes para o bits. Assim, as orientações "esquerda" e "direita" são tiradas da escrita padrão de números em uma notação de valor de posição , de modo que um deslocamento para a esquerda aumenta e um deslocamento para a direita diminui o valor do número - se os dígitos da esquerda forem lidos primeiro, constitui uma orientação big-endian . Desconsiderando os efeitos de limite em ambas as extremidades do registro, as operações de deslocamento aritmético e lógico se comportam da mesma forma, e um deslocamento por posições de 8 bits transporta o padrão de bits pela posição de 1 byte da seguinte maneira:

um deslocamento para a esquerda em 8 posições aumenta o endereço de byte em 1
  • Ordenação Little-endian:
um deslocamento para a direita em 8 posições diminui o endereço de byte em 1
um deslocamento para a esquerda em 8 posições diminui o endereço de byte em 1
  • Pedidos big-endian:
um deslocamento para a direita em 8 posições aumenta o endereço de byte em 1

Mudança aritmética

Mudança aritmética para a esquerda
Mudança aritmética para a direita

Em uma mudança aritmética , os bits que são deslocados para fora de uma das extremidades são descartados. Em um deslocamento aritmético para a esquerda, os zeros são deslocados para a direita; em um deslocamento aritmético para a direita, o bit de sinal (o MSB no complemento de dois) é deslocado para a esquerda, preservando assim o sinal do operando.

Este exemplo usa um registro de 8 bits, interpretado como complemento de dois:

   00010111 (decimal +23) LEFT-SHIFT
=  00101110 (decimal +46)
   10010111 (decimal −105) RIGHT-SHIFT
=  11001011 (decimal −53)

No primeiro caso, o dígito mais à esquerda foi deslocado além do final do registro e um novo 0 foi deslocado para a posição mais à direita. No segundo caso, o 1 mais à direita foi deslocado para fora (talvez no sinalizador de transporte ) e um novo 1 foi copiado na posição mais à esquerda, preservando o sinal do número. Múltiplos turnos às vezes são encurtados para um único turno por um certo número de dígitos. Por exemplo:

   00010111 (decimal +23) LEFT-SHIFT-BY-TWO
=  01011100 (decimal +92)

Um deslocamento aritmético para a esquerda por n é equivalente a multiplicar por 2 n (desde que o valor não transborde ), enquanto um deslocamento aritmético para a direita por n de um valor de complemento de dois é equivalente a tirar o piso da divisão por 2 n . Se o número binário é tratado como complemento para um , então o mesmo shift direita operação resulta na divisão por 2 n e arredondamento em direção a zero .

Mudança lógica

Mudança lógica para a esquerda
Mudança lógica certa

Em uma mudança lógica , os zeros são deslocados para substituir os bits descartados. Portanto, os deslocamentos para a esquerda lógico e aritmético são exatamente os mesmos.

No entanto, como o deslocamento lógico para a direita insere bits de valor 0 no bit mais significativo, em vez de copiar o bit de sinal, é ideal para números binários sem sinal, enquanto o deslocamento aritmético para a direita é ideal para números binários de complemento de dois com sinal .

Mudança circular

Outra forma de deslocamento é o deslocamento circular , rotação bit a bit ou rotação bit .

Girar

Deslocar ou girar circular para a esquerda
Deslocar ou girar circular para a direita

Nessa operação, às vezes chamada de rotate no carry , os bits são "girados" como se as extremidades esquerda e direita do registro estivessem unidas. O valor que é deslocado para a direita durante um deslocamento para a esquerda é o valor que foi deslocado para a esquerda e vice-versa para uma operação de deslocamento para a direita. Isso é útil se for necessário reter todos os bits existentes e é freqüentemente usado na criptografia digital .

Rodar através do transporte

Girar para a esquerda através do transporte
Rotação para a direita através do transporte

Rotate through carry é uma variante da operação de rotação, onde o bit que é deslocado para dentro (em qualquer extremidade) é o valor antigo do sinalizador de carry, e o bit que é deslocado para fora (na outra extremidade) se torna o novo valor de a bandeira de transporte.

Uma única rotação através do carry pode simular uma mudança lógica ou aritmética de uma posição configurando o sinalizador de carry antecipadamente. Por exemplo, se o sinalizador de transporte contém 0, então x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEé um deslocamento lógico para a direita, e se o sinalizador de transporte contém uma cópia do bit de sinal, então x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEé um deslocamento aritmético para a direita. Por esse motivo, alguns microcontroladores, como PICs de baixo custo, apenas giram e giram durante o transporte e não se preocupam com as instruções aritméticas ou lógicas de deslocamento.

Rotate through carry é especialmente útil ao realizar mudanças em números maiores do que o tamanho da palavra nativa do processador , porque se um grande número for armazenado em dois registros, o bit que é deslocado para fora de uma extremidade do primeiro registro deve vir na outra extremidade do o segundo. Com o rotate-through-carry, essa broca é "salva" na bandeira de transporte durante o primeiro turno, pronta para mudar durante o segundo turno sem qualquer preparação extra.

Em linguagens de alto nível

Família C

Em linguagens da família C , os operadores de deslocamento lógico são " <<" para deslocamento à esquerda e " >>" para deslocamento à direita. O número de casas a serem mudadas é fornecido como o segundo argumento para o operador. Por exemplo,

x = y << 2;

atribui xo resultado do deslocamento ypara a esquerda em dois bits, o que é equivalente a uma multiplicação por quatro.

As mudanças podem resultar em comportamento definido pela implementação ou comportamento indefinido , portanto, deve-se tomar cuidado ao usá-las. O resultado da mudança em uma contagem de bits maior ou igual ao tamanho da palavra é um comportamento indefinido em C e C ++. O deslocamento para a direita de um valor negativo é definido pela implementação e não é recomendado por boas práticas de codificação; o resultado do deslocamento para a esquerda de um valor com sinal é indefinido se o resultado não pode ser representado no tipo de resultado.

Em C #, o deslocamento para a direita é um deslocamento aritmético quando o primeiro operando é um inteiro ou longo. Se o primeiro operando for do tipo uint ou ulong, o deslocamento para a direita é um deslocamento lógico.

Mudanças circulares

A família C de linguagens carece de um operador de rotação (embora C ++ 20 forneça std::rotle std::rotr), mas um pode ser sintetizado a partir dos operadores de deslocamento. Deve-se tomar cuidado para garantir que a declaração seja bem formada para evitar comportamento indefinido e ataques de temporização em software com requisitos de segurança. Por exemplo, uma implementação ingênua que gira à esquerda um valor sem sinal de 32 bits xpor nposições é simplesmente:

uint32_t x = ..., n = ...;
uint32_t y = (x << n) | (x >> (32 - n));

No entanto, um deslocamento de 0bits resulta em comportamento indefinido na expressão da mão direita (x >> (32 - n))porque 32 - 0está 32, e 32está fora da faixa [0 - 31]inclusive. Uma segunda tentativa pode resultar em:

uint32_t x = ..., n = ...;
uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;

onde a quantidade de deslocamento é testada para garantir que não introduza um comportamento indefinido. No entanto, a ramificação adiciona um caminho de código adicional e apresenta uma oportunidade para análise de tempo e ataque, o que geralmente não é aceitável em software de alta integridade. Além disso, o código compila para várias instruções de máquina, o que geralmente é menos eficiente do que a instrução nativa do processador.

Para evitar o comportamento indefinido e ramificações no GCC e Clang, o seguinte é recomendado. O padrão é reconhecido por muitos compiladores, e o compilador emitirá uma única instrução de rotação:

uint32_t x = ..., n = ...;
uint32_t y = (x << n) | (x >> (-n & 31));

Existem também intrínsecos específicos do compilador que implementam mudanças circulares , como _rotl8, _rotl16 , _rotr8, _rotr16 no Microsoft Visual C ++ . O Clang fornece alguns intrínsecos de rotação para compatibilidade da Microsoft que sofre os problemas acima. O GCC não oferece intrínsecos de rotação. A Intel também fornece intrínsecos x86 .

Java

Em Java , todos os tipos inteiros são assinados, portanto, os operadores " <<" e " >>" executam deslocamentos aritméticos. Java adiciona o operador " >>>" para realizar deslocamentos lógicos para a direita, mas como as operações lógicas e aritméticas de deslocamento para a esquerda são idênticas para inteiros com sinal, não há <<<operador " " em Java.

Mais detalhes dos operadores de mudança Java:

  • Os operadores <<(deslocamento para a esquerda), >>(deslocamento para a >>>direita com sinal ) e (deslocamento para a direita sem sinal) são chamados de operadores de deslocamento .
  • O tipo da expressão shift é o tipo promovido do operando esquerdo. Por exemplo, aByte >>> 2é equivalente a .((int) aByte) >>> 2
  • Se o tipo promovido do operando à esquerda for int, apenas os cinco bits de ordem inferior do operando à direita serão usados ​​como a distância de deslocamento. É como se o operando à direita fosse submetido a um operador AND lógico bit a bit & com o valor de máscara 0x1f (0b11111). A distância de deslocamento realmente usada está, portanto, sempre na faixa de 0 a 31, inclusive.
  • Se o tipo promovido do operando à esquerda for longo, apenas os seis bits de ordem inferior do operando à direita serão usados ​​como a distância de deslocamento. É como se o operando à direita fosse submetido a um operador AND lógico bit a bit e com o valor de máscara 0x3f (0b111111). A distância de deslocamento realmente usada está, portanto, sempre na faixa de 0 a 63, inclusive.
  • O valor de n >>> sé n deslocou-direita s posições de bits com zero de extensão.
  • Em operações de bit e shift, o tipo byteé convertido implicitamente em int. Se o valor do byte for negativo, o bit mais alto é um, então uns são usados ​​para preencher os bytes extras no int. Então resultará em .byte b1 = -5; int i = b1 | 0x0200;i == -5

JavaScript

JavaScript usa operações bit a bit para avaliar cada uma das duas ou mais unidades, posicionadas em 1 ou 0.

Pascal

Em Pascal, assim como em todos os seus dialetos (como Object Pascal e Standard Pascal ), os operadores lógicos de deslocamento esquerdo e direito são " shl" e " shr", respectivamente. Mesmo para inteiros com shrsinal , se comporta como uma mudança lógica e não copia o bit de sinal. O número de casas a deslocar é fornecido como segundo argumento. Por exemplo, o seguinte atribui x o resultado do deslocamento de y para a esquerda em dois bits:

x := y shl 2;

De outros

Formulários

As operações bit a bit são necessárias principalmente na programação de nível inferior, como drivers de dispositivo, gráficos de baixo nível, montagem de pacote de protocolo de comunicação e decodificação.

Embora as máquinas frequentemente tenham instruções integradas eficientes para realizar operações aritméticas e lógicas, todas essas operações podem ser realizadas combinando os operadores bit a bit e o teste de zero de várias maneiras. Por exemplo, aqui está uma implementação de pseudocódigo da multiplicação do Egito antigo, mostrando como multiplicar dois inteiros arbitrários ae b( amaior que b) usando apenas bitshifts e adição:

c  0
while b  0
    if (b and 1)  0
        c  c + a
    left shift a by 1
    right shift b by 1
return c

Outro exemplo é uma implementação de adição em pseudocódigo, mostrando como calcular a soma de dois inteiros ae busando operadores bit a bit e teste de zero:

while a  0
    c  b and a
    b  b xor a
    left shift c by 1
    a  c
return b

álgebra booleana

Às vezes, é útil simplificar expressões complexas feitas de operações bit a bit. Por exemplo, ao escrever compiladores. O objetivo de um compilador é traduzir uma linguagem de programação de alto nível no código de máquina mais eficiente possível. A álgebra booleana é usada para simplificar expressões bit a bit complexas.

E

  • x & y = y & x
  • x & (y & z) = (x & y) & z
  • x & 0xFFFF = x
  • x & 0 = 0
  • x & x = x

OU

  • x | y = y | x
  • x | (y | z) = (x | y) | z
  • x | 0 = x
  • x | 0xFFFF = 0xFFFF
  • x | x = x

NÃO

  • ~(~x) = x

XOR

  • x ^ y = y ^ x
  • x ^ (y ^ z) = (x ^ y) ^ z
  • x ^ 0 = x
  • x ^ y ^ y = x
  • x ^ x = 0
  • x ^ 0xFFFF = ~x

Além disso, XOR pode ser composto usando as 3 operações básicas (AND, OR, NOT)

  • a ^ b = (a | b) & (~a | ~b)
  • a ^ b = (a & ~b) | (~a & b)

Outros

  • x | (x & y) = x
  • x & (x | y) = x
  • ~(x | y) = ~x & ~y
  • ~(x & y) = ~x | ~y
  • x | (y & z) = (x | y) & (x | z)
  • x & (y | z) = (x & y) | (x & z)
  • x & (y ^ z) = (x & y) ^ (x & z)
  • x + y = (x ^ y) + ((x & y) << 1)
  • x - y = ~(~x + y)

Inversos e resolvendo equações

Pode ser difícil resolver as variáveis ​​na álgebra booleana porque, ao contrário da álgebra regular, várias operações não têm inversas. As operações sem inversas perdem alguns dos bits de dados originais quando são realizadas e não é possível recuperar essas informações ausentes.

  • Tem Inverso
    • NÃO
    • XOR
    • Vire à esquerda
    • Vire à direita
  • Sem inverso
    • E
    • OU
    • Shift Left
    • Shift Right

Ordem de operações

As operações no topo desta lista são executadas primeiro. Veja o artigo principal para uma lista mais completa.

  • ( )
  • ~ -
  • * / %
  • + -
  • << >>
  • &
  • ^
  • |

Veja também

Referências

links externos