Manipulação de bits - Bit manipulation

A manipulação de bits é o ato de manipular bits de forma algorítmica ou outras partes de dados menores que uma palavra . Tarefas de programação de computador que requerem manipulação de bits incluem controle de dispositivo de baixo nível, detecção de erros e algoritmos de correção , compressão de dados , algoritmos de criptografia e otimização . Para a maioria das outras tarefas, as linguagens de programação modernas permitem que o programador trabalhe diretamente com abstrações em vez de bits que representam essas abstrações. O código-fonte que faz a manipulação de bits usa as operações bit a bit : AND, OR, XOR, NOT e possivelmente outras operações análogas aos operadores booleanos; também há mudanças de bits e operações para contar uns e zeros, encontrar um ou zero alto e baixo, definir, redefinir e testar bits, extrair e inserir campos, campos de máscara e zero, reunir e espalhar bits de e para posições ou campos de bit especificados . Os operadores aritméticos inteiros também podem afetar as operações de bits em conjunto com os outros operadores.

A manipulação de bits, em alguns casos, pode evitar ou reduzir a necessidade de fazer um loop em uma estrutura de dados e pode gerar acelerações múltiplas, pois as manipulações de bits são processadas em paralelo.

Terminologia

A manipulação de bits e o bashing de bits são frequentemente usados ​​alternadamente com a manipulação de bits, mas às vezes se referem exclusivamente a maneiras inteligentes ou não óbvias ou usos de manipulação de bits, ou tarefas tediosas ou desafiadoras de manipulação de dados de controle de dispositivo de baixo nível .

O termo bit twiddling data dos primeiros hardwares de computação , em que os operadores de computador faziam ajustes ajustando ou girando os controles do computador. À medida que as linguagens de programação de computador evoluíram, os programadores adotaram o termo para significar qualquer manipulação de dados que envolvesse computação em nível de bit .

Operação bit a bit

Uma operação bit a bit opera em um ou mais padrões de bits ou números binários no nível de seus bits individuais . É uma ação rápida e primitiva diretamente suportada pela unidade central de processamento (CPU) e é usada para manipular valores para comparações e cálculos.

Na maioria dos processadores, a maioria das operações bit a bit é de ciclo único - substancialmente mais rápido do que divisão e multiplicação e ramificações. Enquanto os processadores modernos geralmente executam algumas operações aritméticas e lógicas tão rapidamente 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.

Exemplo de manipulação de bits

Para determinar se um número é uma potência de dois, conceitualmente podemos fazer repetidamente uma divisão inteira por dois até que o número não seja dividido por 2 igualmente; se o único fator restante for 1, o número original era uma potência de 2. Usando operadores de bits e lógicos, há uma expressão simples que retornará verdadeiro (1) ou falso (0):

 bool isPowerOfTwo = (x != 0) && ((x & (x - 1)) == 0);

O segundo método usa o fato de que potências de dois têm um e apenas um conjunto de bits em sua representação binária:

x         == 0...010...0
x-1       == 0...001...1
x & (x-1) == 0...000...0

Se o número não for zero nem uma potência de dois, terá '1' em mais de um lugar:

x         == 0...1...010...0
x-1       == 0...1...001...1
x & (x-1) == 0...1...000...0

Se o código de linguagem assembly embutido for usado, uma instrução que conta o número de 1s ou 0s no operando pode estar disponível; um operando com exatamente um bit '1' é uma potência de 2. No entanto, tal instrução pode ter uma latência maior do que o método bit a bit acima.

Operações de manipulação de bits

Os processadores normalmente fornecem apenas um subconjunto dos operadores de bits úteis. Linguagens de programação não suportam diretamente a maioria das operações de bits, portanto, expressões idiomáticas devem ser usadas para codificá-las. A linguagem de programação 'C', por exemplo, fornece apenas bit a bit AND (&), OR (|), XOR (^) e NOT (~). Fortran fornece AND (.e.), OR (.or.), XOR (.neqv.) E EQV (.eqv.). Algol fornece extração e inserção de campo de bits sintática. Quando as linguagens fornecem operações de bits que não são mapeadas diretamente para as instruções de hardware, os compiladores devem sintetizar a operação a partir dos operadores disponíveis.

Uma operação de bit especialmente útil é contar zeros à esquerda, usado para encontrar o bit de conjunto alto de uma palavra de máquina, embora possa ter nomes diferentes em várias arquiteturas. Não existe um idioma de linguagem de programação simples, portanto, ele deve ser fornecido por uma rotina de biblioteca de sistema ou intrínseca do compilador. Sem esse operador, é muito caro (consulte Encontrar primeiro conjunto # CLZ ) fazer qualquer operação com relação ao bit alto de uma palavra, devido à propagação de transporte assimétrica das operações aritméticas. Felizmente, a maioria das arquiteturas de CPU fornece isso desde meados dos anos 1980. Uma operação de acompanhamento conta uns , também chamada de POPCOUNT, que conta o número de bits definidos em uma palavra de máquina, também é normalmente fornecida como um operador de hardware. Operações de bit mais simples, como conjunto de bits, redefinição, teste e alternância são frequentemente fornecidas como operadores de hardware, mas são facilmente simuladas se não forem - por exemplo (SET R0, 1; LSHFT R0, i; OR x, R0) define bit i no operando x.

Algumas das operações de bits mais úteis e complexas que devem ser codificadas como expressões idiomáticas na linguagem de programação e sintetizadas por compiladores incluem:

  • limpar da posição especificada do bit para cima (deixar a parte inferior da palavra)
  • limpar a partir da posição de bit especificada para baixo (deixar a parte superior da palavra)
  • máscara de bit baixo para baixo (limpar palavra inferior)
  • máscara de bit superior (limpar palavra inferior)
  • extrato de bitfield
  • inserção de bitfield
  • operações de dispersão / coleta de campo de bits que distribuem porções contíguas de um campo de bits sobre uma palavra de máquina ou reúnem campos de bits díspares na palavra em uma parte contígua de um campo de bits (consulte os operadores Intel PEXT / PDEP recentes). Usado por criptografia e codificação de vídeo.
  • inversão de matriz

Algumas operações aritméticas podem ser reduzidas a operações mais simples e operações de bit:

  • reduzir multiplicar por constante para a sequência de shift-add

Multiplicar por 9, por exemplo, é copiar operando, deslocar para cima por 3 (multiplicar por 8) e adicionar ao operando original.

  • reduzir a divisão por constante para a sequência de deslocamento-subtrair

Mascaramento

Uma máscara são dados usados ​​para operações bit a bit , especialmente em um campo de bits .

Usando uma máscara, vários bits em um Byte , nibble , palavra (etc.) podem ser ativados, desativados ou invertidos de ativado para desativado (ou vice-versa) em uma única operação bit a bit. Aplicações mais abrangentes de mascaramento, quando aplicadas condicionalmente às operações, são chamadas de predicação .

Veja também

Referências

Leitura adicional

  • Warren, Henry S. (2013). Hacker's Delight (2ª ed.). Addison – Wesley Professional. p. 512. ISBN 978-0321842688.
  • Knuth, Donald E. (2009). The Art of Computer Programming Volume 4, Fascículo 1: Truques e técnicas bit a bit; Diagramas de decisão binários (1ª ed.). Addison – Wesley Professional. p. 272. ISBN 978-0321580504.( Rascunho do Fascículo 1a disponível para download)

links externos