Casos de uso en el mundo real de operadores bitwise [cerrado]

¿Es extraño?

(value & 0x1) > 0

¿Es divisible por dos (par)?

(value & 0x1) == 0

La programación de bajo nivel es un buen ejemplo. Por ejemplo, es posible que necesite escribir un bit específico en un registro mapeado de memoria para hacer que alguna pieza de hardware haga lo que desea:

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

También, htonl() y htons() se implementan usando los operadores & y | (en máquinas cuya endianidad (orden de bytes) no coincide con el orden de red):

#define htons(a) ((((a) & 0xff00) >> 8) | \
                  (((a) & 0x00ff) << 8))

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

Los uso para obtener valores RGB(A) de valores de color empaquetados, por ejemplo.

Aquí hay algunos modismos comunes que tratan con banderas almacenadas como bits individuales.

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

unsigned int flags = 0;

Establecer la bandera cargable:

flags |= Chargeable;

Clear CallerIDMissing flag:

flags &= ~CallerIDMissing;

Prueba si CallerIDMissing y Chargeable están configurados:

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

}

He utilizado operaciones bitwise en la implementación de un modelo de seguridad para un CMS. Tiene páginas a las que los usuarios pueden acceder si están en grupos apropiados. Un usuario podría estar en varios grupos, por lo que necesitábamos comprobar si había una intersección entre los grupos de usuarios y los grupos de páginas. Así que asignamos a cada grupo un identificador único de potencia de 2, por ejemplo:

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

Nosotros O estos valores juntos, y almacenamos el valor (como un solo int) con la página. Por ejemplo, si se puede acceder a una página grupos A y B, almacenamos el valor 3 (que en binario es 00000011) como el control de acceso de páginas. De la misma manera, almacenamos un valor de identificadores de grupo ORed con un usuario para representar en qué grupos se encuentran.

Así que para comprobar si un usuario determinado puede acceder a una página determinada, solo tiene que Y los valores juntos y comprobar si el valor es distinto de cero. Esto es muy rápido ya que esta comprobación se implementa en una sola instrucción, sin bucle, sin viajes de ida y vuelta de la base de datos.

Cuando tengo un montón de banderas booleanas, me gusta almacenarlas todas en una int.

Los saco usando bitwise-Y. Por ejemplo:

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

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

Etc.

El cifrado es todas las operaciones bitwise.

& = Y:
Enmascara partes específicas.
Está definiendo los bits específicos que se deben mostrar o no se muestra. 0x0 & x borrará todos los bits de un byte mientras que 0xFF no cambiará x. 0x0F mostrará los bits en el mordisco inferior.

Conversión:
Para convertir variables más cortas en variables más largas con identidad de bits es necesario ajustar los bits porque -1 en un int es 0xffffffffff mientras que -1 en un long es 0xFFFFFFFFFFFFFFFF. Preservar la identidad después de aplicar una máscara conversion.

/ = O
Set bits. Los bits se configurarán de forma independiente si ya están configurados. Muchas estructuras de datos (bitfields) tienen banderas como IS_HSET = 0, IS_VSET = 1 que se pueden establecer de forma independiente. Para establecer las banderas, se aplica IS_HSET / IS_VSET (En C y assembly esto es muy conveniente de leer)

^ = XOR
Encuentra bits que son iguales o diferentes.

~ = NOT
Flip bits.

Se puede demostrar que todas las posibles operaciones de bits locales se pueden implementar mediante estas operaciones. Así que si lo desea, puede implementar una instrucción ADD únicamente mediante operaciones de bits.

Algunos hacks maravillosos:

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

Acabo de usar bitwise-XOR (^) hace unos tres minutos para calcular una suma de comprobación para la comunicación en serie con un PLC...

Puede usarlos como una forma rápida y sucia de hash data.

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

Bitwise & se usa para enmascarar/extraer una cierta parte de un byte.

Variable de 1 byte

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

Especialmente el operador shift (>) se utiliza a menudo para los cálculos.

Este es un ejemplo para leer colores de una imagen de mapa de bits en 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 pequeño ejemplo ayude....

La codificación Base64 es un ejemplo. La codificación Base64 se utiliza para representar datos binarios como caracteres imprimibles para el envío a través de sistemas de correo electrónico (y otros fines). La codificación Base64 convierte una serie de bytes de 8 bits en índices de búsqueda de caracteres de 6 bits. Las operaciones de bits, shifting, and'ing, or'ing, not'ing son muy útiles para implementar las operaciones de bits necesarias para la codificación y decodificación de Base64.

Esto, por supuesto, es solo 1 de los innumerables ejemplos.

Estoy sorprendido de que nadie haya elegido la respuesta obvia para la era de Internet. Cálculo de direcciones de red válidas para una subred.

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

En el mundo abstracto del lenguaje moderno de hoy, no demasiados. File IO es uno fácil que viene a la mente, aunque eso está ejerciendo operaciones bitwise en algo ya implementado y no está implementando algo que usa operaciones bitwise. Aún así, como un ejemplo sencillo, este código muestra la eliminación del atributo de solo lectura en un archivo (para que pueda usarse con un nuevo FileStream especificando el modo de archivo.Crear) en 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);
}

En cuanto a las implementaciones personalizadas, aquí hay una ejemplo reciente: He creado un "centro de mensajes" para enviar mensajes seguros de una instalación de nuestra aplicación distribuida a otra. Básicamente, es análogo al correo electrónico, completo con Bandeja de entrada, Bandeja de salida, Enviado, etc, pero también tiene entrega garantizada con recibos de lectura, por lo que hay subcarpetas adicionales más allá de "bandeja de entrada" y "enviado"."Lo que esto significaba era un requisito para mí para definir genéricamente lo que está "en la bandeja de entrada" o lo que está "en la carpeta enviada". De la carpeta enviada, necesito saber lo que se lee y lo que no se lee. De lo que no leídos, necesito saber lo que recibe y lo que no recibió. Utilizo esta información para construir una cláusula where dinámica que filtra una fuente de datos local y muestra la información apropiada.

Así es como se junta la enumeración:

    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
    }

¿Ves lo que esto hace? Por anding ( & ) con el valor de enumeración "Inbox", InboundMemos, sé que Inboundmemosform Orders está en la bandeja de entrada.

Aquí hay una versión reducida del método que compila y devuelve el filtro que define una vista para la carpeta seleccionada actualmente:

    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;
    }

Extremadamente simple, pero una implementación ordenada a un nivel de abstracción que normalmente no requiere operaciones bitwise.

Nadie parece haber mencionado las matemáticas de punto fijo.

(Sí, soy viejo, ok?)

Los operadores bit a bit son útiles para matrices de bucle cuya longitud es potencia de 2. Como muchas personas mencionaron, los operadores bitwise son extremadamente útiles y se utilizan en las banderas , Gráficos, Creación de redes, Cifrado . No solo eso, sino que son extremadamente rápidos. Mi uso favorito es loop una matriz sin condicionales. Supongamos que tiene una matriz basada en un índice cero (por ejemplo, el índice del primer elemento es 0) y necesito hacer un bucle indefinidamente. Por indefinidamente me refiero a ir del primer elemento al último y volver al primero. Una forma de implementar esto es:

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

Este es el enfoque más simple, si desea evitar if declaración, puede utilizar modulus enfoque así:

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

El lado negativo de estos dos métodos es que el operador de módulo es caro, ya que busca un resto después de la división entera. Y el primer método ejecuta una instrucción if en cada iteración. Sin embargo, si la longitud de su matriz es una potencia de 2, puede generar fácilmente una secuencia como 0 .. length - 1 utilizando & (bitwise and) operador como so i & length. Así que sabiendo esto, el código de arriba se convierte

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

Así es como funciona. En el formato binario cada número que es potencia de 2 restada por 1 se expresa solo con unos. Por ejemplo 3 en binario es 11, 7 es 111, 15 es 1111 y así sucesivamente, usted consigue la idea. Ahora, ¿qué sucede si & ¿cualquier número contra un número que consiste solo de unos en binario? Digamos que hacemos esto:

num & 7;

Si num es menor o igual a 7, entonces el resultado será num porque cada bit &-ed con 1 es él mismo. Si num es mayor que 7, durante la operación & la computadora considerará los ceros iniciales de 7 que, por supuesto, permanecerán como ceros después de la operación & solo la parte final permanecerá. Como en el caso de 9 & 7 en binario se verá como

1001 & 0111

El resultado será 0001 que es 1 en decimal y direcciones segundo elemento en matriz.

Normalmente las operaciones bit a bit son más rápidas que hacer multiplicar/dividir. Así que si necesitas multiplicar una variable x por digamos 9, harás x<<3 + x que serían unos ciclos más rápidos que x*9. Si este código está dentro de un ISR, ahorrará tiempo de respuesta.

De manera similar, si desea usar un array como una cola circular, sería más rápido (y más elegante) manejar comprobaciones envolventes con operaciones de bits. (el tamaño de su matriz debe ser una potencia de 2). Por ejemplo: , puede usar tail = ((tail & MASK) + 1) en lugar de tail = ((tail +1) < size) ? tail+1 : 0, si desea insertar/eliminar.

Además, si desea que una bandera de error contenga varios códigos de error juntos, cada bit puede contener un valor separado. Usted puede y con cada código de error individual como un cheque. Esto se usa en códigos de error de Unix.

También un mapa de bits de n-bit puede ser una estructura de datos realmente genial y compacta. Si desea asignar un grupo de recursos de tamaño n, podemos usar n bits para representar el estado actual.

Los uso para opciones de selección múltiple, de esta manera solo almaceno un valor en lugar de 10 o más

También puede ser útil en un modelo relacional sql, digamos que tiene las siguientes tablas: BlogEntry, BlogCategory

Traditonally usted podría crear una relación n-n entre ellos usando una tabla BlogEntryCategory o cuando no hay muchos registros de BlogCategory, puedes usar un valor en BlogEntry para enlazar a varios registros de BlogCategory al igual que lo harías con enumeraciones marcadas, en la mayoría de RDBMS también hay operadores muy rápidos para seleccionar en esa columna 'marcada'...

Es un número x una potencia de 2? (Útil por ejemplo en algoritmos donde un contador se incrementa, y una acción se debe tomar solo número logarítmico de veces)

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

¿Cuál es el bit más alto de un entero x? (Esto, por ejemplo, se puede utilizar para encontrar la potencia mínima de 2 que es mayor 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

¿Cuál es el bit 1 más bajo de un entero x? (Ayuda a encontrar el número de veces divisible por 2.)

x & -x

Cuando solo desea cambiar algunos bits de las salidas de un microcontrolador, pero el registro para escribir es un byte, haga algo como esto (pseudocódigo):

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

Por supuesto, muchos microcontroladores le permiten cambiar cada bit individualmente...

Si alguna vez quieres calcular tu número mod(%) una cierta potencia de 2, puedes usar yourNumber & 2^N-1, que en este caso es lo mismo que yourNumber % 2^N.

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

Esto es probablemente solo útil siendo una alternativa a la operación de módulo con un dividendo muy grande que es 2^N... Pero incluso entonces su aumento de velocidad sobre la operación de módulo es insignificante en mi prueba en. NET 2.0. Sospecho que los compiladores modernos ya realizan optimizaciones como esta. Alguien sabe más sobre esto?

Los he visto usados en sistemas de control de acceso basados en roles.

Hay un uso del mundo real en mi pregunta aquí -
Responder solo a la primera notificación WM_KEYDOWN?

Al consumir un mensaje WM_KEYDOWN en el bit 30 de la api de Windows C especifica el estado de clave anterior. El valor es 1 si la clave está abajo antes de que se envíe el mensaje, o es cero si la clave está arriba

Se utilizan principalmente para operaciones bitwise (sorpresa). Aquí hay algunos ejemplos del mundo real que se encuentran en la base de código PHP.

Codificación de caracteres:

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

Estructuras de datos:

ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK;

Controladores de base de datos:

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

Implementación del compilador:

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

Cada vez que empecé a programar en C, entendí las tablas de verdad y todo eso, pero no todo hizo clic en cómo usarlo hasta que leí este artículo http://www.gamedev.net/reference/articles/article1563.asp (que da ejemplos de la vida real)

No creo que esto cuente como bitwise, pero la matriz de ruby define las operaciones de conjunto a través de los operadores bitwise enteros normales. So [1,2,4] & [1,2,3] # => [1,2]. Del mismo modo para a ^ b #=> set difference y a | b #=> union.

La solución lineal de la torre De Hanoi utiliza operaciones bit a bit para resolver el 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);
    }
}

La explicación de esta solución se puede encontrar aquí