language-agnostic - from - c++ operator
Casos de uso del mundo real de operadores bit a bit (30)
¿Cuáles son algunos casos de uso del mundo real de los siguientes operadores bit a bit?
- Y
- XOR
- NO
- O
& = AND:
Enmascare los 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 nibble inferior.
Conversión:
Para convertir las variables más cortas en 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 (bitfields) tienen indicadores como IS_HSET = 0, IS_VSET = 1 que se pueden establecer de forma independiente. Para establecer los indicadores, aplica IS_HSET | IS_VSET (En C y ensamblado, esto es muy conveniente para leer)
^ = XOR
Encuentra los bits que son iguales o diferentes.
~ = NO
Flip bits.
Se puede demostrar que todas estas operaciones de bits locales posibles pueden implementarse. Entonces, 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
¿Es extraño?
(value & 0x1) > 0
¿Es divisible por dos (pares)?
(value & 0x1) == 0
¿Es un número x una potencia de 2? (Útil por ejemplo en algoritmos donde se incrementa un contador, y una acción debe tomarse solo un 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 usar 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 1 bit más bajo de un entero x ? (Ayuda a encontrar número de veces divisible por 2.)
x & -x
Acabo de utilizar bitwise-XOR ( ^ ) hace unos tres minutos para calcular una suma de comprobación para la comunicación en serie con un PLC ...
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;
Establezca la bandera de carga:
flags |= Chargeable;
Clear CallerIDMissing flag:
flags &= ~CallerIDMissing;
Pruebe si CallerIDMissing y Chargeable están configurados:
if((flags & (CallerIDMissing | Chargeable )) == (CallerIDMissing | Chargeable)) {
}
Bitwise & se utiliza para enmascarar / extraer una determinada parte de un byte.
Variable de 1 byte
01110010
&00001111 Bitmask of 0x0F to find out the lower nibble
--------
00000010
Especialmente el operador de desplazamiento (<< >>) se usa a menudo para los cálculos.
Cada vez que comencé la programación C, entendí las tablas de verdad y todo eso, pero no 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)
Cuando solo quiere cambiar algunos bits de las salidas de un microcontrolador, pero el registro para escribir es un byte, puede 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 ...
Cuando tengo un grupo de indicadores booleanos, me gusta almacenarlos todos 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.
El cifrado es todas operaciones bit a bit.
En el mundo abstracto del lenguaje moderno de hoy, no demasiados. File IO es fácil de recordar, aunque se trata de operaciones bit a bit en algo ya implementado y no está implementando algo que utiliza operaciones bit a bit. Sin embargo, como un ejemplo fácil, este código demuestra la eliminación del atributo de solo lectura en un archivo (para que pueda ser utilizado 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 desde una instalación de nuestra aplicación distribuida a otra. Básicamente, es análogo al correo electrónico, completo con Inbox, Outbox, Sent, 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 qué se lee y qué no se lee. De lo que no se ha leído, necesito saber lo que se recibió y lo que no se recibió. Uso esta información para construir una cláusula where dinámica que filtra un origen de datos local y muestra la información adecuada.
Así es como se arma 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 ejecutar (&) con el valor enum de "Bandeja de entrada", InboundMemos, sé que InboundMemosForMyOrders está en la bandeja de entrada.
Aquí hay una versión reducida 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 normalmente no requiere operaciones bit a bit.
Este es un ejemplo para leer colores de una imagen de mapa de bits en 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 estos pequeños ejemplos ayuden ...
Estoy sorprendido de que nadie eligió la respuesta obvia para la era de Internet. Cálculo de direcciones de red válidas para una subred.
He usado 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 estaban en grupos apropiados. Un usuario podría estar en múltiples grupos, por lo que necesitamos verificar si hubo una intersección entre los grupos de usuarios y los grupos de páginas. Así que asignamos a cada grupo un identificador de poder-de-2 único, 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 los grupos A y B pueden acceder a una página, almacenamos el valor 3 (que en binario es 00000011) a medida que las páginas acceden al control. 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 dado puede acceder a una página dada, solo necesita AND los valores y verificar 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 bucles, sin viajes de ida y vuelta a la base de datos.
La codificación Base64 es un ejemplo. La codificación Base64 se usa 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 bit, shift, and''ing, or''ing, not''ing son muy útiles para implementar las operaciones de bit necesarias para la codificación y decodificación Base64.
Esto, por supuesto, es solo 1 de innumerables ejemplos.
La programación de bajo nivel es un buen ejemplo. Por ejemplo, puede que necesite escribir un bit específico en un registro mapeado en memoria para hacer que una pieza de hardware haga lo que usted 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 usando los htons() & y | operadores (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))
La solución lineal 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 here
Los he visto usar en sistemas de control de acceso basados en roles.
Los operadores bit a bit son útiles para las matrices en bucle cuya longitud es potencia de 2. Como mucha gente mencionó, los operadores bit a bit son extremadamente útiles y se usan en indicadores , gráficos , redes , cifrado . No solo eso, sino que son extremadamente rápidos. Mi uso favorito personal es hacer un ciclo de una matriz sin condicionales . Supongamos que tiene una matriz basada en cero índices (por ejemplo, el índice del primer elemento es 0) y necesita repetirla indefinidamente. Por tiempo indefinido me refiero a pasar 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 instrucció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 inconveniente 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 entera. Y el primer método ejecuta una instrucción if en cada iteración. Sin embargo, con el operador de bit a bit si la longitud de su matriz es una potencia de 2, puede generar fácilmente una secuencia como 0 .. length - 1 usando & (bitwise and) operator como i & length . 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 1111 y así sucesivamente, se entiende la idea. Ahora, ¿qué sucede si tu & cualquier número contra un número que consiste solo en uno en binario? Digamos que hacemos esto:
num & 7;
Si num es más pequeño o igual a 7, el resultado será num porque cada bit & -ed con 1 es él mismo. Si num es mayor que 7, durante la operación & computer considerará los ceros a la izquierda 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 se dirige al segundo elemento en la matriz.
Los uso para obtener valores RGB (A) de valores de color empaquetados, por ejemplo.
Los uso para opciones de selección múltiple, de esta manera solo guardo un valor en lugar de 10 o más
Nadie parece haber mencionado las matemáticas de punto fijo.
(Sí, soy viejo, ¿de acuerdo?)
No creo que esto cuente como bitwise, pero el Array de ruby define las operaciones de conjunto a través de los operadores bitwise enteros normales. Entonces [1,2,4] & [1,2,3] # => [1,2] . Del mismo modo para a ^ b #=> set difference y a | b #=> union a | b #=> union .
Por lo general, las operaciones a nivel de bit son más rápidas que al multiplicar / dividir. Entonces, si necesitas multiplicar una variable x por digamos 9, harás x<<3 + x que sería unos ciclos más rápido que x*9 . Si este código está dentro de un ISR, ahorrará en tiempo de respuesta.
De manera similar, si desea utilizar una matriz como una cola circular, sería más rápido (y más elegante) manejar las revisiones con operaciones de bits. (el tamaño de su matriz debe ser una potencia de 2). Ejemplo: ¿puedes usar tail = ((tail & MASK) + 1) lugar de tail = ((tail +1) < size) ? tail+1 : 0 tail = ((tail +1) < size) ? tail+1 : 0 , si desea insertar / eliminar.
Además, si desea que un indicador de error contenga varios códigos de error, cada bit puede contener un valor por separado. Puede hacerlo con cada código de error individual como una verificación. Esto se usa en los códigos de error de Unix.
Además, 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.
Puede usarlos como una forma rápida y sucia de almacenar datos.
int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;
Se usan 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 bases 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;
Si alguna vez desea calcular su número mod (%) una cierta potencia de 2, puede usar su yourNumber & 2^N-1 , que en este caso es el mismo que su yourNumber % 2^N
number % 16 = number & 15;
number % 128 = number & 127;
Probablemente esto solo sea útil como una alternativa a la operación del módulo con un dividendo muy grande que es 2 ^ N ... Pero aun así su aumento de velocidad sobre la operación del 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?
también puede ser útil en un modelo relacional de SQL, digamos que tiene las siguientes tablas: BlogEntry, BlogCategory
Traditonally podría crear una relación nn entre ellos usando una tabla BlogEntryCategory o cuando no hay tantos registros de BlogCategory puede usar un valor en BlogEntry para vincular a múltiples registros de BlogCategory tal como lo haría con las enumeraciones marcadas, en la mayoría de los RDBMS también hay unos operadores muy rápidos para seleccionar en esa columna ''marcada'' ...
Campos de bits (flags)
Son la forma más eficiente de representar algo cuyo estado está definido por varias propiedades "sí o no". ACL son un buen ejemplo; si tiene, por ejemplo, 4 permisos discretos (leer, escribir, ejecutar, cambiar la política), es mejor almacenar esto en 1 byte en lugar de desperdiciar 4. Estos pueden correlacionarse con los tipos de enumeración en muchos idiomas para mayor comodidad.Comunicación sobre puertos / sockets
Siempre implica sumas de comprobación, paridad, bits de parada, algoritmos de control de flujo, etc., que generalmente dependen de los valores lógicos de bytes individuales en oposición a los valores numéricos, ya que el medio solo puede transmitir un bit a la vez.Compresión, Encriptación
Ambos dependen en gran medida de los algoritmos bit a bit. Mire el algoritmo de deflate para ver un ejemplo: todo está en bits, no en bytes.Máquinas de estado finito
Hablo principalmente del tipo integrado en algún hardware, aunque también se pueden encontrar en el software. Estos son de naturaleza combinatoria: literalmente se pueden "compilar" en un grupo de compuertas lógicas, por lo que deben expresarse comoAND,OR,NOT, etc.Gráficos Aquí apenas hay espacio suficiente para acceder a todas las áreas donde se utilizan estos operadores en la programación de gráficos.
XOR(o^) es particularmente interesante porque aplicar la misma entrada por segunda vez deshace la primera. Las GUI antiguas solían confiar en esto para resaltar la selección y otras superposiciones, con el fin de eliminar la necesidad de rediseños 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.