Casos de uso del mundo real de operadores bit a bit [cerrado]

¿Cuáles son algunos casos de uso en el mundo real de los siguientes operadores bit a bit?

• Y
• XOR
• NO
• O
• Desplazamiento a la izquierda / derecha

• Campos de bits (banderas)
  Son la forma más eficiente de representar algo cuyo estado está definido por varias propiedades "sí o no". Las ACL son un buen ejemplo; Si tiene 4 permisos discretos (leer, escribir, ejecutar, cambiar la política), es mejor almacenar esto en 1 byte en lugar de desperdiciar 4. Estos pueden asignarse a tipos de enumeración en muchos idiomas para mayor comodidad.

• La comunicación a través de puertos / sockets
  siempre implica sumas de verificación, paridad, bits de parada, algoritmos de control de flujo, etc., que generalmente dependen de los valores lógicos de bytes individuales en lugar de valores numéricos, ya que el medio solo puede transmitir un bit a un momento.

• Compresión, cifrado
  Ambos dependen en gran medida de algoritmos bit a bit. Mire el algoritmo de desinflado para ver un ejemplo: todo está en bits, no en bytes.

• Máquinas de estado finito
  Estoy hablando principalmente del tipo incrustado en alguna pieza de hardware, aunque también se pueden encontrar en el software. Estos son combinatoria en la naturaleza - que podría estar recibiendo, literalmente, "compilado" a un montón de puertas lógicas, así que tienen que ser expresada como AND, OR, NOT, etc.

• Gráficos Aquí apenas hay suficiente espacio para acceder a todas las áreas donde se utilizan estos operadores en la programación de gráficos. XOR(o ^) es particularmente interesante aquí porque aplicar la misma entrada una segunda vez deshacerá la primera. Las GUI más antiguas solían confiar en esto para resaltar la selección y otras superposiciones, a fin de eliminar la necesidad de redibujos costosos. Todavía son útiles en protocolos de gráficos lentos (es decir, escritorio remoto).

Esos fueron solo los primeros ejemplos que se me ocurrieron; esta no es una lista exhaustiva.

¿Es extraño?

(value & 0x1) > 0

¿Es divisible por dos (par)?

(value & 0x1) == 0

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 de carga:

flags |= Chargeable;

Borrar CallerIDMissing flag:

flags &= ~CallerIDMissing;

Pruebe si CallerIDMissing y Chargeable están configurados:

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

}

He utilizado operaciones bit a bit en la implementación de un modelo de seguridad para un CMS. Tenía páginas a las que los usuarios podían acceder si se encontraban en grupos apropiados. Un usuario podría estar en varios grupos, por lo que necesitábamos verificar si había una intersección entre los grupos de usuarios y los grupos de páginas. Entonces 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

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

Entonces, para verificar si un usuario determinado puede acceder a una página determinada, solo necesita AND los valores juntos y verificar si el valor no es cero. Esto es muy rápido ya que esta verificación se implementa en una sola instrucción, sin bucles, sin ida y vuelta de la base de datos.

La programación de bajo nivel es un buen ejemplo. Es posible que, por ejemplo, necesite escribir un bit específico en un registro mapeado en memoria para hacer que una 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

Además, htonl()y htons()se implementan utilizando los operadores &y |(en máquinas cuya endianness (orden de bytes) no coincide con el orden de la 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.

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

Los saco usando bitwise-AND. Por ejemplo:

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

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

etc.

& = Y:
enmascarar bits específicos.
Está definiendo los bits específicos que deberían mostrarse o no mostrarse. 0x0 & x borrará todos los bits en 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 0xFFFFFFFF mientras que -1 en un largo es 0xFFFFFFFFFFFFFFFF. Para preservar la identidad, aplica una máscara después de la conversión.

| = O
Establecer bits. Los bits se establecerán de forma independiente si ya están configurados. Muchas estructuras de datos (campos de bits) tienen indicadores como IS_HSET = 0, IS_VSET = 1 que se pueden configurar de forma independiente. Para establecer las banderas, aplica IS_HSET | IS_VSET (en C y ensamblaje esto es muy conveniente de leer)

^ = XOR
Encuentra bits que son iguales o diferentes.

~ = NO
Voltear bits.

Se puede demostrar que todas estas posibles operaciones de bits locales pueden implementarse mediante estas operaciones. Entonces, si lo desea, puede implementar una instrucción ADD únicamente mediante operaciones de bit.

Algunos hacks maravillosos:

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

El cifrado es todas las operaciones bit a bit.

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

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

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

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 de turno (<< >>) se usa a menudo para los cálculos.

Este es un ejemplo para leer colores de una imagen de mapa de bits en formato 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 estos pequeños ejemplos ayuden ...

En el mundo abstracto del lenguaje moderno de hoy, no demasiados. File IO es fácil de recordar, aunque está ejerciendo operaciones bit a bit en algo ya implementado y no está implementando algo que utiliza operaciones bit a bit. Aún así, como un ejemplo sencillo, este código demuestra la eliminación del atributo de solo lectura en un archivo (para que pueda usarse con un nuevo FileStream que especifique FileMode.Create) 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 un ejemplo reciente: creé 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 significó fue un requisito para mí para definir genéricamente qué está "en la bandeja de entrada" o qué está "en la carpeta enviada". De la carpeta enviada, necesito saber qué se lee y qué no se lee. De lo que no se ha leído, necesito saber qué se recibe y qué no. Utilizo esta información para crear una cláusula where dinámica que filtre una fuente de datos local y muestre la información adecuada.

Así es como se ensambla 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 hace esto? Al llamar (&) con el valor de enumeración "Inbox", InboundMemos, sé que InboundMemosForMyOrders está en la bandeja de entrada.

Aquí hay una versión resumida del método que crea 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 generalmente no requiere operaciones bit a bit.

La codificación Base64 es un ejemplo. La codificación Base64 se utiliza para representar datos binarios como caracteres imprimibles para enviar 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 bit, desplazamiento, y 'o' no-son son muy útiles para implementar las operaciones de bit necesarias para la codificación y decodificación Base64.

Por supuesto, esto es solo 1 de innumerables ejemplos.

Me sorprende 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

Por lo general, las operaciones bit a bit son más rápidas que multiplicar / dividir. Entonces, si necesita multiplicar una variable x por decir 9, hará lo x<<3 + xque sería unos ciclos más rápido quex*9 . Si este código está dentro de un ISR, ahorrará tiempo de respuesta.

Del mismo modo, si desea utilizar una matriz como una cola circular, sería más rápido (y más elegante) manejar cheques envolventes con operaciones de bits sabios. (el tamaño de su matriz debe ser una potencia de 2). Por ejemplo: puedes usar en tail = ((tail & MASK) + 1)lugar detail = ((tail +1) < size) ? tail+1 : 0 , si desea insertar / eliminar.

Además, si desea que un indicador de error mantenga juntos varios códigos de error, cada bit puede contener un valor separado. Puede Y con cada código de error individual como un cheque. Esto se usa en los códigos de error de Unix.

También un mapa de bits de n bits 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.

Nadie parece haber mencionado matemáticas de punto fijo.

(Sí, soy viejo, ¿vale?)

¿Es un número xuna potencia de 2? (Útil, por ejemplo, en algoritmos en los que se incrementa un contador, y una acción se debe tomar solo logarítmicamente varias 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 1bit más bajo de un entero x? (Ayuda a encontrar el número de veces divisible por 2.)

x & -x

Los operadores a nivel de bits son útiles para la formación de bucles de matrices cuya longitud es una potencia de 2. Como muchas personas mencionaron, los operadores a nivel de bits son extremadamente útiles y se utilizan en Banderas , Gráficos , Redes , Cifrado . No solo eso, sino que son extremadamente rápidos. Mi uso favorito personal es hacer un loop de una matriz sin condicionales . Suponga que tiene una matriz basada en índice cero (por ejemplo, el índice del primer elemento es 0) y necesita 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 la declaración if , puede usar el enfoque de módulo de la siguiente manera:

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 costoso, ya que busca un resto después de la división de enteros. Y el primer método ejecuta una instrucción if en cada iteración. Con el operador bit a bit, sin embargo, si la longitud de su matriz es una potencia de 2, puede generar fácilmente una secuencia como 0 .. length - 1utilizando el &operador (bit a bit y) como tal i & length. Entonces, 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 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 1111y así sucesivamente, se entiende la idea. Ahora, ¿qué sucede si &cualquier número contra un número que consta solo de unos en binario? Digamos que hacemos esto:

num & 7;

Si numes menor o igual a 7, el resultado será numporque cada bit &con 1 es él mismo. Si numes 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 permanecerá la parte final. Como en el caso de 9 & 7en binario se verá como

1001 & 0111

el resultado será 0001, que es 1 en decimal y se dirige al segundo elemento en la matriz.

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, supongamos que tiene las siguientes tablas: BlogEntry, BlogCategory

Tradicionalmente, podría crear una relación nn entre ellos utilizando una tabla BlogEntryCategory o cuando no hay tantos registros BlogCategory, podría usar un valor en BlogEntry para vincular a múltiples registros BlogCategory al igual que lo haría con enumeraciones marcadas, en la mayoría de RDBMS también hay un operador muy rápido para seleccionar en esa columna 'marcada' ...

Cuando solo desea cambiar algunos bits de las salidas de un microcontrolador, pero el registro para escribir es un byte, debe hacer 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 desea calcular su número de mod (%) una cierta potencia de 2, puede usar yourNumber & 2^N-1, que en este caso es el mismo que yourNumber % 2^N.

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

Esto probablemente solo sea útil como 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 utilizados en sistemas de control de acceso basados ​​en roles.

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

Cuando se consume un mensaje WM_KEYDOWN en Windows C, el bit 30 especifica el estado de la clave anterior. El valor es 1 si la tecla está abajo antes de enviar el mensaje, o es cero si la tecla está arriba

Se utilizan principalmente para operaciones bit a bit (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 comencé a programar en C, entendí las tablas de verdad y todo eso, pero no todo hizo clic en cómo usarlo realmente 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 bit a bit, pero Ruby's Array define las operaciones de conjunto a través de los operadores enteros normales a nivel de bit. Por lo tanto [1,2,4] & [1,2,3] # => [1,2]. Del mismo modo para a ^ b #=> set differencey a | b #=> union.

La solución lineal de Tower Of 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í.