Casos de uso no mundo real de operadores bit a bit [fechados]

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

• E
• XOR
• NÃO
• OU
• Deslocamento Esquerda / Direita

• 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 quatro permissões discretas (leitura, gravação, execução, alteração de política), é melhor armazená-lo em 1 byte em vez de desperdiçar 4. Elas podem ser mapeadas para tipos de enumeração em vários idiomas para maior comodidade.

• Comunicação através de portas / soquetes
  Sempre envolve somas de verificação, paridade, bits de parada, algoritmos de controle de fluxo e assim por diante, que geralmente dependem dos valores lógicos de bytes individuais em oposição aos valores numéricos, pois o meio pode ser capaz de transmitir apenas um bit em um tempo.

• Compactação, criptografia
  Ambos dependem fortemente de algoritmos bit a bit. Veja o algoritmo deflate como exemplo - tudo está em bits, não em bytes.

• Máquinas de estado finito
  Estou falando principalmente do tipo incorporado em alguma peça de hardware, embora elas também possam ser encontradas em software. Estes são combinatória na natureza - eles podem ser literalmente ficando "compilado" para baixo para um monte de portas lógicas, então eles têm que ser expressa como AND, OR, NOT, etc.

• Gráficos Não há espaço suficiente aqui para entrar em todas as áreas em que esses operadores são usados ​​na programação gráfica. XOR(ou ^) é particularmente interessante aqui, porque aplicar a mesma entrada uma segunda vez desfará a primeira. As GUIs mais antigas costumavam contar com isso para destacar a seleção e outras sobreposições, a fim de eliminar a necessidade de redesenhos dispendiosos. Eles ainda são úteis em protocolos gráficos lentos (ou seja, área de trabalho remota).

Esses foram apenas os primeiros exemplos que inventei - essa dificilmente é uma lista exaustiva.

Isso é estranho?

(value & 0x1) > 0

É divisível por dois (par)?

(value & 0x1) == 0

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

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

unsigned int flags = 0;

Defina o sinalizador de cobrança:

flags |= Chargeable;

Limpar sinalizador CallerIDMissing:

flags &= ~CallerIDMissing;

Teste se CallerIDMissing e 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. Ele tinha páginas que poderiam ser acessadas pelos usuários se eles estivessem em grupos apropriados. Como um usuário pode estar em vários grupos, é necessário verificar se há uma interseção entre os grupos de usuários e os grupos de páginas. Portanto, atribuímos a cada grupo um identificador de potência 2 exclusivo, por exemplo:

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

OR esses valores juntos e armazenamos o valor (como um único int) com a página. Por exemplo, se uma página puder ser acessada pelos grupos A e B, armazenamos o valor 3 (que em binário é 00000011) como controle de acesso à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, basta AND AND os 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 ida e volta ao banco de dados.

A programação de baixo nível é um bom exemplo. Você pode, por exemplo, precisar escrever um bit específico em um registro mapeado na memória para fazer com que algum hardware faça o que você deseja:

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 os operadores &e |(em máquinas cuja endianness (ordem de bytes) não corresponde à ordem da 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 cores compactados, por exemplo.

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

Eu os pego usando AND bit a bit. Por exemplo:

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

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

etc.

& = AND:
mascarar bits específicos.
Você está definindo os bits específicos que devem ser exibidos ou não. 0x0 e x limparão todos os bits em um byte, enquanto 0xFF não mudará x. 0x0F exibirá os bits na mordidela inferior.

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

| = OR
Defina bits. Os bits serão definidos independentemente se já estiverem definidos. Muitas estruturas de dados (campos de bits) possuem sinalizadores como IS_HSET = 0, IS_VSET = 1, que podem ser configurados independentemente. Para definir os sinalizadores, aplique IS_HSET | IS_VSET (em C e montagem, é muito conveniente ler isso)

^ = XOR
Encontre bits iguais ou diferentes.

~ = NÃO
Virar bits.

Pode-se mostrar que todas as operações de bits locais possíveis podem ser implementadas por essas operações. Portanto, se você quiser, pode implementar uma instrução ADD apenas por operações de bits.

Alguns hacks maravilhosos:

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

Criptografia são todas as operações bit a bit.

Você pode usá-los como uma maneira rápida e suja de hash de dados.

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

Eu apenas usei bitwise-XOR ( ^) cerca de três minutos atrás para calcular uma soma de verificação para comunicação serial com um PLC ...

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

Variável de 1 byte

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

Especialmente o operador de turno (<< >>) é frequentemente usado para cálculos.

Este é um exemplo para ler cores de uma imagem de bitmap no formato de bytes

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 ....

No mundo abstrato da linguagem moderna de hoje, não muitos. O arquivo IO é fácil de lembrar, embora esteja exercendo operações bit a bit em algo já implementado e não esteja implementando algo que usa 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);
}

Quanto às implementações personalizadas, aqui está um exemplo recente: criei um "centro de mensagens" para enviar mensagens seguras de uma instalação de nosso aplicativo distribuído para outra. Basicamente, é análogo ao e-mail, completo com Caixa de entrada, Caixa de saída, Enviado etc., mas também possui entrega garantida com recibos de leitura, para que haja subpastas adicionais além de "caixa de entrada" e "enviado". O que isso representou foi um requisito para eu definir genericamente o que está "na caixa de entrada" ou o que está "na pasta enviada". Na pasta enviada, preciso saber o que é lido e o que não é lido. Do que não foi lido, preciso saber o que é recebido e o que não é recebido. Eu uso essas informações para criar uma cláusula where dinâmica que filtra uma fonte de dados local e exibe as informações apropriadas.

Veja como o enum é montado:

    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? Anding (&) com o valor de enumeração "Inbox", InboundMemos, eu sei que InboundMemosForMyOrders está na caixa de entrada.

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

    private string GetFilterForView(MemoView view, DefaultableBoolean readOnly)
    {
        string filter = string.Empty;
        if((view & MemoView.InboundMemos) == MemoView.InboundMemos)
        {
            filter = "<inbox filter conditions>";

            if((view & MemoView.InboundMemosForMyOrders) == MemoView.InboundMemosForMyOrders)
            {
                filter += "<my memo filter conditions>";
            }
        }
        else if((view & MemoView.SentMemosAll) == MemoView.SentMemosAll)
        {
            //all sent items have originating system = to local
            filter = "<memos leaving current system>";

            if((view & MemoView.Outbox) == MemoView.Outbox)
            {
                ...
            }
            else
            {
                //sent sub folders
                filter += "<all sent items>";

                if((view & MemoView.SentMemosNotReceived) == MemoView.SentMemosNotReceived)
                {
                    if((view & MemoView.SentMemosReceivedNotRead) == MemoView.SentMemosReceivedNotRead)
                    {
                        filter += "<not received and not read conditions>";
                    }
                    else
                        filter += "<received and not read conditions>";
                }
            }
        }

        return filter;
    }

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

A codificação Base64 é um exemplo. A codificação Base64 é usada para representar dados binários como caracteres imprimíveis para enviar por sistemas de email (e outros fins). A codificação Base64 converte uma série de bytes de 8 bits em índices de pesquisa de caracteres de 6 bits. As operações de bits, deslocamento e andamento, ou não, são muito úteis para implementar as operações de bits necessárias para a codificação e decodificação Base64.

É claro que isso é apenas um dos inúmeros exemplos.

Estou surpreso que ninguém tenha escolhido a resposta óbvia para a era da Internet. Cálculo de endereços de rede válidos para uma sub-rede.

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

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, faça o x<<3 + xque seriam alguns ciclos mais rápidos que x*9. Se esse código estiver dentro de um ISR, você economizará tempo de resposta.

Da mesma forma, se você deseja usar uma matriz como uma fila circular, seria mais rápido (e mais elegante) lidar com cheques de contorno com operações pouco inteligentes. (o tamanho do seu array deve ter uma potência de 2). Por exemplo:, você pode usar em tail = ((tail & MASK) + 1)vez de tail = ((tail +1) < size) ? tail+1 : 0, se desejar inserir / excluir.

Além disso, se você desejar 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 uma verificação. 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ê deseja alocar um pool de recursos do tamanho n, podemos usar n-bits para representar o status atual.

Parece que ninguém mencionou matemática de ponto fixo.

(Sim, eu sou velho, ok?)

Um número é xuma potência de 2? (Útil, por exemplo, em algoritmos em que um contador é incrementado e uma ação deve ser executada apenas o número logarítmico de vezes)

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

Qual é o bit mais alto de um número inteiro x? (Isso, por exemplo, pode ser usado para encontrar a potência mínima de 2 que é 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 1bit mais baixo de um número inteiro x? (Ajuda a encontrar o número de vezes divisível por 2.)

x & -x

Operadores bit a bit são úteis para loop de matrizes cujo tamanho é a potência 2. Como muitas pessoas mencionaram, os operadores bit a bit são extremamente úteis e são usados ​​em sinalizadores , gráficos , redes , criptografia . Não só isso, mas eles são extremamente rápidos. Meu uso favorito pessoal é fazer um loop de uma matriz sem condicionais . Suponha que você tenha uma matriz baseada em índice zero (por exemplo, o índice do primeiro elemento é 0) e precise fazer um loop indefinidamente. Por indefinidamente, quero dizer passar do primeiro elemento ao último e retornar ao 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ê deseja evitar a instrução if , 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;
}

A desvantagem desses dois métodos é que o operador do módulo é caro, pois procura um restante 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 da sua matriz for uma potência de 2, você poderá gerar facilmente uma sequência como 0 .. length - 1usando o &operador (bit a bit e) dessa forma i & length. Então, sabendo disso, o código de cima se torna

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 , todo número que é o poder de 2 subtraído por 1 é expresso apenas com um. Por exemplo 3 em binário é 11, 7 é 111, 15 é 1111e assim por diante, você entendeu. Agora, o que acontece se você tiver &algum número em relação a um número composto apenas por números binários? Digamos que fazemos isso:

num & 7;

Se numfor menor ou igual a 7, o resultado será numporque cada bit &com 1 é o próprio. Se numfor maior que 7, durante a &operação, o computador considerará os zeros à esquerda do 7, que, obviamente, permanecerão como zeros após a &operação, apenas a parte à direita permanecerá. Como no caso de 9 & 7em binário, parecerá

1001 & 0111

o resultado será 0001, que é 1 em decimal e aborda o segundo elemento na matriz.

Eu os uso para opções de seleção múltipla, dessa forma, armazeno apenas um valor em vez de 10 ou mais

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

tradicionalmente, você poderia criar um relacionamento nn entre eles usando uma tabela BlogEntryCategory ou, quando não houver muitos registros BlogCategory, você poderia usar um valor no BlogEntry para vincular a vários registros BlogCategory, como faria com enumerações sinalizadas, na maioria dos RDBMS também existem operadores muito rápidos para selecionar nessa coluna 'sinalizada' ...

Quando você deseja alterar apenas alguns bits das saídas de um microcontrolador, mas o registro no qual 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

Obviamente, muitos microcontroladores permitem alterar cada bit individualmente ...

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

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

Isso provavelmente é útil apenas como uma alternativa à 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 é desprezível no meu teste no .NET 2.0. Suspeito que os compiladores modernos já executem otimizações como esta. Alguém sabe mais sobre isto?

Eu os vi usados ​​em sistemas de controle de acesso baseados em funções.

Existe um uso no mundo real na minha pergunta aqui -
Responder apenas à primeira notificação WM_KEYDOWN?

Ao consumir uma mensagem WM_KEYDOWN nas janelas C api bit 30 especifica o estado da chave anterior. O valor é 1 se a chave estiver pressionada antes do envio da mensagem ou será zero se a chave estiver ativada

Eles são usados ​​principalmente para operações bit a bit (surpresa). Aqui estão alguns exemplos do mundo real encontrados na base de código 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 banco de dados:

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 iniciei a programação C, entendi as tabelas verdadeiras e tudo mais, mas nem tudo funcionou até o momento em que li 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 Ruby Array define operações de conjunto por meio dos operadores inteiros normais em bits. Então [1,2,4] & [1,2,3] # => [1,2]. Da mesma forma para a ^ b #=> set differencee a | b #=> union.

A solução linear da 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