aplicaciones prácticas de operaciones bit a bit [cerrado]

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

Aunque todo el mundo parece estar enganchado al caso de uso de las banderas, esa no es la única aplicación de los operadores bit a bit (aunque probablemente la más común). Además, C # es un lenguaje de nivel lo suficientemente alto como para que otras técnicas probablemente se usen con poca frecuencia, pero aún así vale la pena conocerlas. Esto es lo que puedo pensar:

Los operadores <<y >>pueden multiplicarse rápidamente por una potencia de 2. Por supuesto, el optimizador .NET JIT probablemente hará esto por usted (y cualquier compilador decente de otro lenguaje también), pero si realmente está preocupado por cada microsegundo, podría escribir esto para estar seguro.

Otro uso común de 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 desea confundir a los inexpertos, como cuando responde a una pregunta de tarea. :)

Sin embargo, en cualquier código real, estará mucho mejor usando la multiplicación, porque tiene una legibilidad mucho mejor y el JIT lo optimiza shly las shrinstrucciones de todos modos, por lo que no hay una penalización de rendimiento.

Hay bastantes trucos curiosos relacionados con el ^operador (XOR). En realidad, este es un operador muy poderoso, debido a las siguientes propiedades:

• A^B == B^A
• A^B^A == B
• Si sabe, A^Bentonces es imposible saber qué son Ay B, pero si conoce uno de ellos, puede calcular el otro.
• El operador no sufre desbordamientos como multiplicación / división / suma / resta.

Un par de trucos que he visto usando este operador:

Intercambio de dos variables enteras sin una variable intermedia:

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 solo una variable adicional por elemento. Esto tendrá poco uso en C #, pero podría resultar útil para la programación de bajo nivel de sistemas embebidos donde cada byte cuenta.

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

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

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

Para recorrer desde el final, solo necesita cambiar la primera línea de FirstItema LastItem. Ese es otro ahorro de memoria allí mismo.

Otro lugar donde uso el ^operador de manera regular 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();
    }
}

Utilizo operadores bit a bit por seguridad en mis aplicaciones. Almacenaré los diferentes niveles dentro de un Enum:

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

Y luego asigne a un usuario sus niveles:

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

Y luego verifique los permisos en la acción que se está realizando:

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

No sé qué tan práctico es resolver un sudoku que consideres, pero supongamos que lo es.

Imagina que quieres escribir un solucionador de sudoku o incluso un programa simple, que te muestre el tablero y te permita resolver el rompecabezas tú mismo, pero asegure que los movimientos sean legales.

Lo más probable es que el tablero en sí esté representado por una matriz bidimensional como:

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

Valor 0significa que la celda aún está vacía y los valores del rango [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 obedezcan las reglas, no importa, pero en un solucionador podría.

Puede mantener matrices de máscaras de bits, que almacenan información sobre los números que ya están insertados en cada fila, cada columna ay 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 al patrón de bits, 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 #, puede calcular el patrón de bits de esta manera ( valuees un uint):

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

En la línea anterior 1ucorrespondiente al patrón de bits 00000000 00000000 00000000 00000001se desplaza hacia la izquierda porvalue - 1 . Si, por ejemplo value == 5, obtiene

00000000 00000000 00000000 00010000

Al principio, la máscara para cada fila, columna y cuadro es 0. Cada vez que pones algún número en el tablero, actualizas la máscara, por lo 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 desde 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áscaramaskForNumbersSetInRow[3] ve así:

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 bit a bit o operador (| ). Primero crea un patrón de bits correspondiente al valor 5

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

y luego usa operator |para configurar el bit en la máscaramaskForNumbersSetInRow[3]

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

o usando una forma más corta

maskForNumbersSetInRow[3] |= bitpattern;

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

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

Si desea verificar, si hay algún valor 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 desea verificar si el valor 3 está en la fila, puede hacerlo 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 muestran métodos para establecer un nuevo valor en el tablero, mantener actualizadas las máscaras de bits adecuadas y 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;

}

Teniendo las máscaras, puedes comprobar si la mudanza es legal así:

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

Docenas de ejemplos de juegos de bits aquí

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

Si alguna vez necesita comunicarse con el hardware, necesitará usar un poco de juguete en algún momento.

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

Muchas cosas

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, mayor rendimiento.
3. No puedo escribir un tutorial sobre el terreno, pero estoy seguro de que están ahí fuera.

Se pueden usar para una gran cantidad de aplicaciones diferentes, aquí hay una pregunta que publiqué anteriormente aquí, que usa operaciones bit a bit:

AND bit a bit, pregunta OR inclusiva bit a bit, en Java

Para ver otros ejemplos, eche un vistazo a (digamos) 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 con signo a sin signo).

el artículo de MSN aquí ->

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

es útil.

Y, aunque este enlace:

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

es muy técnico, lo cubre todo.

HTH

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

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

Debo decir que uno de los usos más comunes es la modificación de campos de bits para comprimir datos. Esto se ve principalmente en programas que intentan ser económicos con paquetes.

Ejemplo de compresión de red usando campos de bits

Una de las cosas más frecuentes para las que los uso en C # es producir códigos hash. Hay algunos métodos de hash razonablemente buenos que los utilizan. Por ejemplo, para una clase coordinada con una X y una Y que fueran ambas entradas, 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 es producido por un objeto igual (asumiendo que la igualdad significa que los parámetros X e Y son iguales en ambos objetos comparados) mientras que tampoco produce patrones en conflicto para objetos de bajo valor (probablemente más común en la mayoría de las aplicaciones).

Otro es combinar enumeraciones de banderas. P.ejRegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase

Hay algunas operaciones de bajo nivel que comúnmente no son necesarias cuando se codifica 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 tenía que escribir ese código.

Hay algunas técnicas de alteración de bits, como redondear al número binario más cercano (por ejemplo, redondear 1010 a 10000):

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

Que son útiles cuando los necesitas, pero que tienden a no ser muy comunes.

Finalmente, también puede usarlos para optimizar las matemáticas como en << 1lugar de, * 2pero lo incluyo solo para decir que generalmente es una mala idea, ya que oculta la intención del código real, no ahorra casi nada en el rendimiento y puede ocultar algunos errores sutiles. .

Tipo binario. Hubo problemas en los que la implementación utilizaba un operador de división en lugar de un operador de desplazamiento de bits. Esto provocó que BS fallara después de que la colección llegara a tamaños superiores a 10,000,000

Los usará por varias razones:

• almacenar (¡y verificar!) los indicadores de opciones de una manera eficiente en la memoria
• Si realiza programación computacional, es posible que desee considerar la optimización de algunas de sus operaciones utilizando operaciones bit a bit en lugar de operadores matemáticos (tenga cuidado con los efectos secundarios).
• Código gris !
• creando valores enumerados

Estoy seguro de que puedes pensar en otros.

Dicho esto, a veces es necesario preguntarse: ¿vale la pena el esfuerzo por aumentar la memoria y el rendimiento? Después de escribir ese tipo de código, déjelo reposar un rato y vuelva a leerlo. Si tiene problemas con él, vuelva a escribir con un código más fácil de mantener.

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

Mejor aún, pida a otra persona que lo lea y documente extensamente.

¡Juegos!

En el pasado, lo usé para representar las piezas de un jugador de Reversi. Es 8X8, por lo que me tomó un longtipo y, por ejemplo, si quieres saber dónde están todas las piezas a bordo, orambos jugadores son piezas.
Si desea todos los pasos posibles de un jugador, diga a la derecha: usted >>representa las piezas del jugador en uno y ANDcon las piezas del oponente para verificar si ahora hay unos comunes (eso significa que hay una pieza del oponente a su derecha). Entonces sigues haciendo eso. si vuelve a sus propias piezas, no se mueva. Si llega a un lugar despejado, puede moverse allí y capturar todas las piezas en el camino.
(Esta técnica se usa ampliamente en muchos tipos de juegos de mesa, incluido el ajedrez)