Casos de uso do mundo real de operadores bit a bit

Quais são alguns casos de uso do mundo real dos seguintes operadores bitwise?

  • E
  • XOR
  • NÃO
  • OU

  • Campos de bits (sinalizadores)
    Eles são a maneira mais eficiente de representar algo cujo estado é definido por várias propriedades “sim ou não”. ACLs são um bom exemplo; Se você tiver, digamos, 4 permissions discretas (leia, escreva, execute, altere a política), é melhor armazená-lo em 1 byte em vez de desperdício 4. Eles podem ser mapeados para tipos de enumeração em vários idiomas para maior conveniência.

  • Comunicação através de portas / sockets
    Sempre envolve sums de verificação, paridade, bits de parada, algoritmos de controle de stream e assim por diante, que geralmente dependem dos valores lógicos de bytes individuais em oposição a valores numéricos, pois o meio só pode transmitir um bit de cada vez.

  • Compressão, criptografia
    Ambos são altamente dependentes de algoritmos bitwise. Olhe para o algoritmo deflate para um exemplo – tudo está em bits, não em bytes.

  • Máquinas de estados finitos
    Estou falando basicamente do tipo embutido em algum hardware, embora eles também possam ser encontrados em software. Estes são de natureza combinatória – eles podem estar literalmente sendo “compilados” para um grupo de portas lógicas, então eles devem ser expressos como AND , OR , NOT , etc.

  • Gráficos Não há espaço suficiente aqui para entrar em todas as áreas onde esses operadores são usados ​​na programação de charts. XOR (ou ^ ) é particularmente interessante aqui porque aplicar a mesma input uma segunda vez desfará a primeira. As GUIs mais antigas costumavam depender disso para realçar a seleção e outras sobreposições, a fim de eliminar a necessidade de redesenhos custosos. Eles ainda são úteis em protocolos charts lentos (por exemplo, área de trabalho remota).

Esses foram apenas os primeiros exemplos que eu criei – isso dificilmente é uma lista exaustiva.

É estranho?

 (value & 0x1) > 0 

É divisível por dois (par)?

 (value & 0x1) == 0 

A programação de baixo nível é um bom exemplo. Você pode, por exemplo, precisar escrever um bit específico em um registrador mapeado na memory para fazer com que alguma peça de hardware faça o que você quer:

 volatile uint32_t *register = (volatile uint32_t *)0x87000000; uint32_t value; uint32_t set_bit = 0x00010000; uint32_t clear_bit = 0x00001000; value = *register; // get current value from the register value = value & ~clear_bit; // clear a bit value = value | set_bit; // set a bit *register = value; // write it back to the register 

Além disso, htonl() e htons() são implementados usando o & e | operadores (em máquinas cujo endianness (ordem de Byte) não corresponde à ordem de rede):

 #define htons(a) ((((a) & 0xff00) >> 8) | \ (((a) & 0x00ff) << 8)) #define htonl(a) ((((a) & 0xff000000) >> 24) | \ (((a) & 0x00ff0000) >> 8) | \ (((a) & 0x0000ff00) << 8) | \ (((a) & 0x000000ff) << 24)) 

Eu os uso para obter valores RGB (A) de valores de colors compactados, por exemplo.

Aqui estão alguns idiomas comuns lidando com sinalizadores armazenados como bits individuais.

 enum CDRIndicators { Local = 1 << 0, External = 1 << 1, CallerIDMissing = 1 << 2, Chargeable = 1 << 3 }; unsigned int flags = 0; 

Definir o sinalizador de cobrança:

 flags |= Chargeable; 

Limpar o sinalizador CallerIDMissing:

 flags &= ~CallerIDMissing; 

Teste se o CallerIDMissing e o Chargeable estão definidos:

 if((flags & (CallerIDMissing | Chargeable )) == (CallerIDMissing | Chargeable)) { } 

Eu usei operações bit a bit na implementação de um modelo de segurança para um CMS. Tinha páginas que poderiam ser acessadas pelos usuários se estivessem em grupos apropriados. Um usuário poderia estar em vários grupos, então precisávamos verificar se havia uma interseção entre os grupos de usuários e os grupos de páginas. Então, atribuímos a cada grupo um identificador exclusivo de poder-2, por exemplo:

 Group A = 1 --> 00000001 Group B = 2 --> 00000010 Group C = 3 --> 00000100 

Nós OR esses valores juntos e armazenamos o valor (como um único int) com a página. Por exemplo, se uma página pode ser acessada pelos grupos A e B, armazenamos o valor 3 (que em binário é 00000011) como o controle de access às páginas. Da mesma maneira, armazenamos um valor de identificadores de grupo ORed com um usuário para representar em quais grupos eles estão.

Portanto, para verificar se um determinado usuário pode acessar uma determinada página, você precisa apenas AND dos valores juntos e verificar se o valor é diferente de zero. Isso é muito rápido, pois essa verificação é implementada em uma única instrução, sem loop, sem roundtrip de database.

Quando eu tenho um monte de sinalizadores booleanos, gosto de armazená-los todos em um int.

Eu tiro eles usando bitwise-AND. Por exemplo:

 int flags; if (flags & 0x10) { // Turn this feature on. } if (flags & 0x08) { // Turn a second feature on. } 

etc.

Criptografia é toda operação bit a bit.

& = AND:
Mascara pedaços específicos.
Você está definindo os bits específicos que devem ser exibidos ou não exibidos. 0x0 & x apagará todos os bits em um byte enquanto 0xFF não alterará x. 0x0F mostrará os bits no nibble inferior.

Conversão:
Para converter variables ​​mais curtas em outras mais longas com identidade de bit, é necessário ajustar os bits porque -1 em um int é 0xFFFFFFFF, enquanto que -1 em um long é 0xFFFFFFFFFFFFFFFF. Para preservar a identidade, você aplica uma máscara após a conversão.

| = OR
Definir bits. Os bits serão definidos indefinidamente se já estiverem definidos. Muitas estruturas de dados (bitfields) possuem sinalizadores como IS_HSET = 0, IS_VSET = 1, que podem ser definidos indepentemente. Para definir os sinalizadores, aplique IS_HSET | IS_VSET (em C e assembly isso é muito conveniente para ler)

^ = XOR
Encontre bits que são iguais ou diferentes.

~ = NÃO
Flip bits.

Pode ser mostrado que todas as possíveis operações de bits locais podem ser implementadas por essas operações. Então, se você gosta, você pode implementar uma instrução ADD somente por operações de bits.

Alguns hacks maravilhosos:

http://www.ugcs.caltech.edu/~wnoise/base2.html
http://www.jjj.de/bitwizardry/bitwizardrypage.html

Eu usei bitwise-XOR ( ^ ) há cerca de três minutos para calcular uma sum de verificação para comunicação serial com um CLP …

Você pode usá-los como um modo rápido e sujo de dados de hash.

 int a = 1230123; int b = 1234555; int c = 5865683; int hash = a ^ b ^ c; 

Bitwise & é usado para mascarar / extrair uma certa parte de um byte.

1 byte variável

  01110010 &00001111 Bitmask of 0x0F to find out the lower nibble -------- 00000010 

Especialmente o operador de deslocamento (<< >>) é freqüentemente usado para cálculos.

Este é um exemplo para ler colors de uma imagem de bitmap em formato de byte

 byte imagePixel = 0xCCDDEE; /* Image in RRGGBB format R=Red, G=Green, B=Blue */ //To only have red byte redColour = imagePixel & 0xFF0000; /*Bitmasking with AND operator */ //Now, we only want red colour redColour = (redColour >> 24) & 0xFF; /* This now returns a red colour between 0x00 and 0xFF. 

Espero que este pequeno exemplo ajude ….

Codificação Base64 é um exemplo. A codificação Base64 é usada para representar dados binários como caracteres imprimíveis para envio por sistemas de email (e outras finalidades). A codificação Base64 converte uma série de bytes de 8 bits em índices de pesquisa de caracteres de 6 bits. Operações de bit, shifting, and’ing, or’ing, not’ing são muito úteis para implementar as operações de bit necessárias para codificação e decodificação Base64.

Isto, obviamente, é apenas um dos inúmeros exemplos.

Estou surpreso ninguém escolheu a resposta óbvia para a era da Internet. Calculando endereços de rede válidos para uma sub-rede.

http://www.topwebhosts.org/tools/netmask.php

No mundo abstraído da linguagem moderna de hoje, não são muitos. O File IO é fácil, mas está exercitando operações bit-a-bit em algo já implementado e não está implementando algo que use operações bit a bit. Ainda assim, como um exemplo fácil, esse código demonstra a remoção do atributo somente leitura em um arquivo (para que possa ser usado com um novo FileStream especificando FileMode.Create) em c #:

 //Hidden files posses some extra attibutes that make the FileStream throw an exception //even with FileMode.Create (if exists -> overwrite) so delete it and don't worry about it! if(File.Exists(targetName)) { FileAttributes attributes = File.GetAttributes(targetName); if ((attributes & FileAttributes.ReadOnly) == FileAttributes.ReadOnly) File.SetAttributes(targetName, attributes & (~FileAttributes.ReadOnly)); File.Delete(targetName); } 

No que diz respeito às implementações personalizadas, segue um exemplo recente: criei um “centro de mensagens” para enviar mensagens seguras de uma instalação do nosso aplicativo distribuído para outra. Basicamente, é análogo ao e-mail, completo com Caixa de input, Caixa de saída, Enviados, etc., mas também tem entrega garantida com recibos de leitura, portanto, há subpastas adicionais além da “checkbox de input” e “enviadas”. O que isso significou foi um requisito para eu definir genericamente o que está “na checkbox de input” ou “na pasta enviada”. Da pasta enviada, preciso saber o que é lido e o que não foi lido. Do que não foi lido, preciso saber o que foi recebido e o que não foi recebido. Eu uso essa informação para construir uma cláusula where dinâmica que filtra uma fonte de dados local e exibe as informações apropriadas.

Veja como o enum é formado:

  public enum MemoView :int { InboundMemos = 1, // 0000 0001 InboundMemosForMyOrders = 3, // 0000 0011 SentMemosAll = 16, // 0001 0000 SentMemosNotReceived = 48, // 0011 SentMemosReceivedNotRead = 80, // 0101 SentMemosRead = 144, // 1001 Outbox = 272, //0001 0001 0000 OutBoxErrors = 784 //0011 0001 0000 } 

Você vê o que isso faz? Por anding (&) com o valor de enum “Inbox”, InboundMemos, eu sei que InboundMemosForMyOrders está na checkbox de input.

Aqui está uma versão resumida do método que cria e retorna o filtro que define uma exibição para a pasta atualmente selecionada:

  private string GetFilterForView(MemoView view, DefaultableBoolean readOnly) { string filter = string.Empty; if((view & MemoView.InboundMemos) == MemoView.InboundMemos) { filter = ""; if((view & MemoView.InboundMemosForMyOrders) == MemoView.InboundMemosForMyOrders) { filter += ""; } } else if((view & MemoView.SentMemosAll) == MemoView.SentMemosAll) { //all sent items have originating system = to local filter = ""; if((view & MemoView.Outbox) == MemoView.Outbox) { ... } else { //sent sub folders filter += ""; if((view & MemoView.SentMemosNotReceived) == MemoView.SentMemosNotReceived) { if((view & MemoView.SentMemosReceivedNotRead) == MemoView.SentMemosReceivedNotRead) { filter += ""; } else filter += ""; } } } return filter; } 

Extremamente simples, mas uma implementação simples em um nível de abstração que normalmente não requer operações bit a bit.

Ninguém parece ter mencionado matemática de ponto fixo.

(Sim, sou velho, ok?)

Os operadores bit-a-bit são úteis para arrays em loop cujo comprimento é o poder de 2. Como muitas pessoas mencionaram, os operadores bitwise são extremamente úteis e são usados ​​em Flags , Graphics , Networking , Encryption . Não só isso, mas eles são extremamente rápidos. Meu uso favorito pessoal é fazer o loop de um array sem condicionais . Suponha que você tenha uma matriz baseada em índice zero (por exemplo, o índice do primeiro elemento é 0) e você precisa fazer um loop indefinidamente. Por indefinidamente, quero dizer ir do primeiro elemento para o último e retornar para o primeiro. Uma maneira de implementar isso é:

 int[] arr = new int[8]; int i = 0; while (true) { print(arr[i]); i = i + 1; if (i >= arr.length) i = 0; } 

Esta é a abordagem mais simples, se você quiser evitar a declaração if , você pode usar a abordagem de módulo da seguinte forma:

 int[] arr = new int[8]; int i = 0; while (true) { print(arr[i]); i = i + 1; i = i % arr.length; } 

O lado negativo desses dois methods é que o operador de módulo é caro, pois procura um resto após a divisão inteira. E o primeiro método executa uma instrução if em cada iteração. Com o operador bit a bit, no entanto, se o comprimento de sua matriz for uma potência de 2, você poderá gerar facilmente uma sequência como 0 .. length - 1 usando o operador & (bit a bit) e assim como i & length . Então, sabendo disso, o código de cima torna-se

 int[] arr = new int[8]; int i = 0; while (true){ print(arr[i]); i = i + 1; i = i & (arr.length - 1); } 

Aqui está como isso funciona. No formato binário , cada número que é de 2 subtraído por 1 é expresso apenas com uns. Por exemplo, 3 em binário é 11 , 7 é 111 , 15 é 1111 e assim por diante, você começa a idéia. Agora, o que acontece se você & qualquer número em relação a um número que consiste apenas de um em binário? Vamos dizer que fazemos isso:

 num & 7; 

Se num for menor ou igual a 7, o resultado será num porque cada bit & -ed com 1 é ele mesmo. Se num for maior que 7, durante o computador de operação & irá considerar os zeros à esquerda de 7, que naturalmente permanecerão como zeros após & operação, somente a parte final permanecerá. Como no caso de 9 & 7 em binário, será semelhante

 1001 & 0111 

o resultado será 0001, que é 1 em decimal e endereça o segundo elemento em array.

Normalmente, as operações bit a bit são mais rápidas do que multiplicar / dividir. Portanto, se você precisar multiplicar uma variável x por 9, você fará x<<3 + x que seria alguns ciclos mais rápido que x*9 . Se este código estiver dentro de um ISR, você economizará no tempo de resposta.

Da mesma forma, se você quiser usar uma matriz como uma fila circular, seria mais rápido (e mais elegante) lidar com verificações de contorno com operações de bit wise. (o tamanho da sua matriz deve ser uma potência de 2). Por exemplo:, você pode usar tail = ((tail & MASK) + 1) vez de tail = ((tail +1) < size) ? tail+1 : 0 tail = ((tail +1) < size) ? tail+1 : 0 , se você deseja inserir / excluir.

Além disso, se você quiser que um sinalizador de erro mantenha vários códigos de erro juntos, cada bit poderá conter um valor separado. Você pode AND com cada código de erro individual como um cheque. Isso é usado nos códigos de erro do Unix.

Além disso, um bitmap de n bits pode ser uma estrutura de dados muito legal e compacta. Se você quiser alocar um pool de resources de tamanho n, podemos usar um n-bits para representar o status atual.

Eu os uso para várias opções de seleção, dessa forma eu só armazeno um valor em vez de 10 ou mais

também pode ser útil em um modelo relacional de sql, digamos que você tenha as seguintes tabelas: BlogEntry, BlogCategory

traditonally você poderia criar um relacionamento nn entre eles usando uma tabela BlogEntryCategory ou quando não há tantos registros de BlogCategory você poderia usar um valor em BlogEntry para vincular a vários registros de BlogCategory como faria com enums sinalizados, na maioria dos RDBMS também existem um operador muito rápido para selecionar nessa coluna “sinalizada” …

É um número x uma potência de 2? (Útil, por exemplo, em algoritmos onde um contador é incrementado, e uma ação deve ser tomada apenas em logaritmo de vezes)

 (x & (x - 1)) == 0 

Qual é o bit mais alto de um inteiro x ? (Isso pode ser usado, por exemplo, para encontrar a potência mínima de 2 maior que x )

 x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); return x - (x >>> 1); // ">>>" is unsigned right shift 

Qual é o menor 1 bit de um inteiro x ? (Ajuda a encontrar o número de vezes divisível por 2.)

 x & -x 

Quando você quer apenas alterar alguns bits das saídas de um microcontrolador, mas o registrador para gravar é um byte, você faz algo assim (pseudocódigo):

 char newOut = OutRegister & 0b00011111 //clear 3 msb's newOut = newOut | 0b10100000 //write '101' to the 3 msb's OutRegister = newOut //Update Outputs 

Claro, muitos microcontroladores permitem que você mude cada bit individualmente …

Se você quiser calcular o seu número mod (%) uma certa potência de 2, você pode usar yourNumber & 2^N-1 , que neste caso é o mesmo que yourNumber % 2^N

 number % 16 = number & 15; number % 128 = number & 127; 

Isso provavelmente só é útil como uma alternativa para a operação de módulo com um dividendo muito grande que é 2 ^ N … Mas mesmo assim seu aumento de velocidade sobre a operação de módulo é insignificante no meu teste no .NET 2.0. Eu suspeito que os compiladores modernos já realizam otimizações como essa. Alguém sabe mais sobre isto?

Eu os vi usados ​​em sistemas de controle de access baseados em function.

Existe um mundo real em minha pergunta aqui –
Responda apenas à primeira notificação WM_KEYDOWN?

Ao consumir uma mensagem WM_KEYDOWN nas janelas, o bit 30 da API C especifica o estado da chave anterior. O valor é 1 se a chave estiver inativa antes que a mensagem seja enviada ou será zero se a chave estiver ativa

Eles são usados ​​principalmente para operações bitwise (surpresa). Aqui estão alguns exemplos reais encontrados na codebase do PHP.

Codificação de caracteres:

 if (s <= 0 && (c & ~MBFL_WCSPLANE_MASK) == MBFL_WCSPLANE_KOI8R) { 

Estruturas de dados:

 ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK; 

Drivers de database:

 dbh->transaction_flags &= ~(PDO_TRANS_ACCESS_MODE^PDO_TRANS_READONLY); 

Implementação do compilador:

 opline->extended_value = (opline->extended_value & ~ZEND_FETCH_CLASS_MASK) | ZEND_FETCH_CLASS_INTERFACE; 

Sempre que comecei a programar em C, eu entendia as tabelas de verdade e tudo mais, mas nem todos os cliques com como usá-la até eu ler este artigo http://www.gamedev.net/reference/articles/article1563.asp (que dá exemplos da vida real)

Eu não acho que isso conta como bit a bit, mas o Array de Ruby define operações através dos operadores bit a bit inteiro normal. Então [1,2,4] & [1,2,3] # => [1,2] . Da mesma forma para a ^ b #=> set difference e a | b #=> union a | b #=> union .

A solução linear Tower Of Hanoi usa operações bit a bit para resolver o problema.

 public static void linear(char start, char temp, char end, int discs) { int from,to; for (int i = 1; i < (1 << discs); i++) { from = (i & i-1) % 3; to = ((i | i-1) + 1) % 3; System.out.println(from+" => "+to); } } 

A explicação para esta solução pode ser encontrada aqui