aplicaciones prácticas de operaciones bit a bit

Question

1. ¿Para qué ha utilizado las operaciones bit a bit?
2. ¿por qué son tan útiles?
3. ¿alguien puede recomendar un tutorial MUY simple?

Answer 1

Aunque parece que todo el mundo está enganchado al uso de banderas, esa no es la única aplicación de operadores bit a bit (aunque probablemente la más común). También C# es un lenguaje de nivel lo suficientemente alto como para que otras técnicas sean raramente utilizadas, pero aún así vale la pena conocerlas. Esto es lo que ocurre:

---

Los << y >> los operadores pueden multiplicarse rápidamente por una potencia de 2. Por supuesto, el optimizador de .NET JIT probablemente lo hará por usted (y cualquier compilador decente de otro idioma también), pero si realmente te preocupas por cada microsegundo, puedes escribir esto para estar seguro.

Otro uso común para estos operadores es rellenar dos enteros de 16 bits en un entero de 32 bits. Me gusta:

int Result = (shortIntA << 16) | shortIntB; 

Esto es común para la interfaz directa con las funciones de Win32, que a veces usan este truco por razones heredadas.

Y, por supuesto, estos operadores son útiles cuando se quiere confundir a los inexpertos, como cuando se responde a una pregunta de tarea.:)

En ningún código real, aunque podrás mucho mejor mediante el uso de la multiplicación lugar, porque tiene una mejor legibilidad y el JIT optimiza a shl y shr instrucciones de todos modos por lo que no hay pérdida de rendimiento.

---

Un buen número de trucos curiosos se ocupan de la ^ operador (XOR). Esto es en realidad un operador muy potente, debido a las siguientes propiedades:

• A^B == B^A
• A^B^A == B
• Si conoces A^B entonces es imposible decir qué A y B son, pero si conoce una de ellas , puedes calcular el otro.
• El operador no sufre desbordamientos como multiplicación/división/suma/resta.

Un par de trucos que he visto el uso de este operador:

Intercambio de dos variables enteras sin una variable intermediaria:

A = A^B // A is now XOR of A and B 
B = A^B // B is now the original A 
A = A^B // A is now the original B 

lista doblemente enlazada con una sola variable adicional por artículo. Esto tendrá poco uso en C#, pero podría ser útil para la programación de bajo nivel de sistemas integrados donde cada byte cuenta.

La idea es que realice un seguimiento del puntero para el primer elemento; el puntero para el último artículo; y para cada artículo, realiza un seguimiento de pointer_to_previous^pointer_to_next. De esta forma puede recorrer la lista desde cualquier extremo, pero la sobrecarga es solo la mitad de una lista vinculada tradicional. Aquí está el código C++ para desplazamiento:

ItemStruct *CurrentItem = FirstItem, *PreviousItem=NULL; 
while ( CurrentItem != NULL) 
{ 
    // Work with CurrentItem->Data 

    ItemStruct *NextItem = CurrentItem->XorPointers^PreviousItem; 
    PreviousItem = CurrentItem; 
    CurrentItem = NextItem; 
} 

Atravesar desde el final sólo tiene que cambiar la primera línea de FirstItem a LastItem. Es otro ahorro de memoria allí mismo.

Otro lugar donde utilizo regularmente el operador ^ en C# es cuando tengo que calcular un HashCode para mi tipo que es un tipo compuesto. Me gusta:

class Person 
{ 
    string FirstName; 
    string LastName; 
    int Age; 

    public int override GetHashCode() 
    { 
     return (FirstName == null ? 0 : FirstName.GetHashCode())^
      (LastName == null ? 0 : LastName.GetHashCode())^
      Age.GetHashCode(); 
    } 
} 

Answer 2

Utilizo operadores bit a bit para la seguridad en mis aplicaciones. Voy a almacenar los diferentes niveles dentro de una enumeración:

[Flags] 
public enum SecurityLevel 
{ 
    User = 1, // 0001 
    SuperUser = 2, // 0010 
    QuestionAdmin = 4, // 0100 
    AnswerAdmin = 8 // 1000 
} 

y luego asignar un usuario a sus niveles:

// Set User Permissions to 1010 
// 
// 0010 
// | 1000 
// ---- 
// 1010 
User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin; 

y después comprobar los permisos en la acción que se realiza:

// Check if the user has the required permission group 
// 
// 1010 
// & 1000 
// ---- 
// 1000 
if((User.Permissions & SecurityLevel.AnswerAdmin) == SecurityLevel.AnswerAdmin) 
{ 
    // Allowed 
} 

Answer 3

1. Se pueden usar para pasar muchos argumentos a una función a través de una variable de tamaño limitado.
2. Las ventajas son una baja sobrecarga de memoria o un bajo costo de memoria: por lo tanto, un mayor rendimiento.
3. No puedo escribir un tutorial en el momento, pero están ahí, estoy seguro.

Answer 4

Pueden ser utilizados para una carga completa de diferentes aplicaciones, aquí hay una pregunta previamente que he publicado aquí, que utiliza operaciones bit a bit:

Bitwise AND, Bitwise Inclusive OR question, in Java

Para otros ejemplos, echar un vistazo a (decir) enumeraciones marcadas.

En mi ejemplo, estaba usando operaciones bit a bit para cambiar el rango de un número binario de -128 ... 127 a 0..255 (cambiando su representación de firmado a no firmado).

el artículo MSN aquí ->

http://msdn.microsoft.com/en-us/library/6a71f45d%28VS.71%29.aspx

es útil.

Y, aunque este vínculo:

http://weblogs.asp.net/alessandro/archive/2007/10/02/bitwise-operators-in-c-or-xor-and-amp-amp-not.aspx

es muy técnico, que está cubriendo todo.

HTH

Answer 5

cada vez que tenga una opción de 1 o más en la combinación de elementos continuación, bit a bit suele ser una solución fácil.

Algunos ejemplos incluyen bits de seguridad (en espera en la muestra de Justin ..), los días de programación, etc.

Answer 6

Yo tendría que decir que uno de los usos más comunes está modificando campos de bits para comprimir los datos. En su mayoría, esto se ve en los programas que intentan ser económicos con los paquetes.

Ejemplo de network compression using bitfields

Answer 7

Una de las cosas más frecuentes que los utilizan para en C# está produciendo hashcodes. Hay algunos métodos de hash razonablemente buenos que los usan. P.ej. para una clase de coordenadas con una X una Y que eran ambos enteros I podría usar:

public override int GetHashCode() 
{ 
    return x^((y << 16) | y >> 16); 
} 

Esto genera rápidamente un número que está garantizado para ser igual cuando se produce por un objeto igual (asumiendo que la igualdad significa tanto X y los parámetros Y son los mismos en ambos objetos comparados) y no producen patrones de choque para objetos de bajo valor (probablemente sean los más comunes en la mayoría de las aplicaciones).

Otro es la combinación de enumeraciones de banderas. P.ej. RegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase

Existen algunas operaciones de bajo nivel que normalmente no son necesarias cuando se está codificando en un marco como .NET (por ejemplo, en C# no necesitaré escribir código para convertir UTF-8 a UTF-16, está ahí para mí en el marco), pero por supuesto alguien tuvo que escribir ese código.

Hay algunas técnicas de bits haciendo girar, como redondeando al número binario más cercano (por ejemplo redonda hasta 1010 a 10000):

 unchecked 
     { 
      --x; 
      x |= (x >> 1); 
      x |= (x >> 2); 
      x |= (x >> 4); 
      x |= (x >> 8); 
      x |= (x >> 16); 
      return ++x; 
     } 

Qué son útiles cuando los necesite, pero que tiende a no ser muy común.

Por último, también puede utilizarlos para las matemáticas micro-optimización, tales como << 1 en lugar de * 2 pero incluir que sólo para decir que es generalmente una mala idea, ya que oculta la intención del código real, ahorra casi nada en el rendimiento, y puede ocultar algunos errores sutiles.

Answer 8

Clasificación binaria. Hubo problemas donde la implementación usaba un operador de división en lugar de un operador de cambio de bits. Esto causó que BS fallara después de que la colección llegara a tamaños superiores a 10,000,000

Answer 9

Si alguna vez necesita comunicarse con el hardware, tendrá que utilizar bit twiddling en algún momento.

Extrayendo los valores RGB de un valor de píxel.

Tantas cosas

Answer 10

no sé qué tan práctico, resolver un sudoku considera que son, pero vamos a suponer que es.

Imagine que desea escribir un sudoku solver o incluso un simple programa, que le muestra el tablero y le permite resolver el rompecabezas usted mismo, pero asegura que los movimientos sean legales.

la propia placa, muy probablemente será representado por una matriz bidimensional como:

uint [, ] theBoard = new uint[9, 9]; 

Valor 0 significa que la célula es todavía vacío y los valores de la gama [1u, 9u] son ​​los valores reales en el tablero.

Ahora imagina que quieres comprobar si algún movimiento es legal. Obviamente, puedes hacerlo con algunos bucles, pero las máscaras de bits te permiten hacer las cosas mucho más rápido. En un programa simple que solo asegura que se obedecen las reglas, no importa, pero en un solucionador podría.

Puede mantener matrices de máscaras de bits, que almacenan información acerca de los números que ya están insertados en cada fila, cada columna a y cada cuadro de 3x3.

uint [] maskForNumbersSetInRow = new uint[9]; 

uint [] maskForNumbersSetInCol = new uint[9]; 

uint [, ] maskForNumbersSetInBox = new uint[3, 3]; 

La asignación del número a la bitpattern, con un bit correspondiente a ese conjunto de números, es muy simple

1 -> 00000000 00000000 00000000 00000001 
2 -> 00000000 00000000 00000000 00000010 
3 -> 00000000 00000000 00000000 00000100 
... 
9 -> 00000000 00000000 00000001 00000000 

En C#, se puede calcular la bitpattern esta manera (value es un uint):

uint bitpattern = 1u << (int)(value - 1u); 

En la línea anterior 1u correspondiente a la bitpattern 00000000 00000000 00000000 00000001 es Shifte d dejado por value - 1. Si, por ejemplo value == 5, se obtiene

00000000 00000000 00000000 00010000

Al principio, la máscara para cada fila, columna y caja es 0. Cada vez que coloca un número en la pizarra, actualiza la máscara, de modo que se establece el bit correspondiente al nuevo valor.

Supongamos que inserta el valor 5 en la fila 3 (las filas y columnas están numeradas de 0). La máscara para la fila 3 se almacena en maskForNumbersSetInRow[3]. Supongamos también que antes de la inserción ya había números {1, 2, 4, 7, 9} en la fila 3. El patrón de bits en la máscara maskForNumbersSetInRow[3] se parece a esto:

00000000 00000000 00000001 01001011 
bits above correspond to:9 7 4 21 

El objetivo es establecer el bit correspondiente al valor 5 en esta máscara. Puede hacerlo usando bitwise u operador (|). En primer lugar se crea un patrón de bits que corresponde al valor 5

uint bitpattern = 1u << 4; // 1u << (int)(value - 1u) 

y luego utiliza el operator | para establecer el bit en la máscara maskForNumbersSetInRow[3]

maskForNumbersSetInRow[3] = maskForNumbersSetInRow[3] | bitpattern; 

o el uso de la forma más corta

maskForNumbersSetInRow[3] |= bitpattern; 

00000000 00000000 00000001 01001011 
       | 
00000000 00000000 00000000 00010000 
       = 
00000000 00000000 00000001 01011011 

Ahora su máscara indica que hay valores {1, 2, 4, 5, 7, 9} en esta fila (fila 3).

Si desea verificar, si algún valor está en la fila, puede usar operator & para verificar si el bit correspondiente está configurado en la máscara. Si el resultado de ese operador aplicado a la máscara y un patrón de bits, correspondiente a ese valor, es distinto de cero, el valor ya está en la fila. Si el resultado es 0, el valor no está en la fila.

Por ejemplo, si usted quiere comprobar si el valor 3 se encuentra en la fila, se puede hacer que de esta manera:

uint bitpattern = 1u << 2; // 1u << (int)(value - 1u) 
bool value3IsInRow = ((maskForNumbersSetInRow[3] & bitpattern) != 0); 

00000000 00000000 00000001 01001011 // the mask 
       | 
00000000 00000000 00000000 00000100 // bitpattern for the value 3 
       = 
00000000 00000000 00000000 00000000 // the result is 0. value 3 is not in the row. 

A continuación se presentan métodos para establecer un nuevo valor en el tablero, el mantenimiento de máscaras de bits apropiados hasta hasta la fecha y para verificar si un movimiento es legal.

public void insertNewValue(int row, int col, uint value) 
{ 

    if(!isMoveLegal(row, col, value)) 
     throw ... 

    theBoard[row, col] = value; 

    uint bitpattern = 1u << (int)(value - 1u); 

    maskForNumbersSetInRow[row] |= bitpattern; 

    maskForNumbersSetInCol[col] |= bitpattern; 

    int boxRowNumber = row/3; 
    int boxColNumber = col/3; 

    maskForNumbersSetInBox[boxRowNumber, boxColNumber] |= bitpattern; 

} 

Tener las máscaras, se puede comprobar si el movimiento es legal como esto:

public bool isMoveLegal(int row, int col, uint value) 
{ 

    uint bitpattern = 1u << (int)(value - 1u); 

    int boxRowNumber = row/3; 
    int boxColNumber = col/3; 

    uint combinedMask = maskForNumbersSetInRow[row] | maskForNumbersSetInCol[col] 
         | maskForNumbersSetInBox[boxRowNumber, boxColNumber]; 

    return ((theBoard[row, col] == 0) && ((combinedMask & bitpattern) == 0u); 
} 

Answer 11

Vamos a usar ellos por varias razones: (! Y comprobación)

• almacenamiento Indicadores de opción de forma eficiente en la memoria
• Si realiza una programación computacional, es posible que desee considerar la optimización de algunas de sus operaciones mediante el uso de operaciones bit a bit en lugar de m operadores matemáticos (cuidado con los efectos secundarios)
• Gray Code!
• creación de valores enumerados

Estoy seguro de que puede pensar en otros.

Dicho esto, a veces hay que preguntarse: la potencia de memoria y rendimiento vale la pena. Después de escribir ese tipo de código, déjalo descansar un rato y vuelve a él. Si tiene problemas con esto, vuelva a escribir con un código más fácil de mantener.

Por otro lado, a veces tiene mucho sentido usar operaciones bit a bit (piense en criptografía).

Mejor aún, haz que alguien más lo lea y documente extensamente.

Answer 12

Juegos!

Detrás en los días, lo usé para representar las piezas de un jugador de Reversi. Es 8X8 así que me tomó un tipo long, y que, por ejemplo, si quieres saber dónde están todas las piezas a bordo, tienes or ambas piezas de jugadores.
Si desea todos los pasos posibles de un jugador, diga a la derecha - >> la representación de las piezas del jugador por uno, y AND con las piezas del oponente para comprobar si ahora hay 1 comunes (eso significa que hay una pieza oponente para tu derecho). Entonces sigues haciendo eso. si vuelves a tus propias piezas, no hay movimiento. Si llega a un punto claro, puede moverse allí y capturar todas las piezas en el camino.
(Esta técnica se utiliza ampliamente, en muchos tipos de juegos de mesa, incluyendo ajedrez)

Answer 13

Dozens of bit twiddling examples here

El código está en C, pero se puede adaptar fácilmente a C#