logical - null c# operator

Aplicaciones prácticas de operaciones bitwise

Question

1. ¿Para qué has usado las operaciones bitwise?
2. ¿Por qué son tan útiles?
3. ¿Alguien puede recomendar un tutorial MUY simple?

Answer 1

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 están ahí, estoy seguro.

Answer 2

¡Juegos!

En los días, lo usé para representar las piezas de un jugador Reversi. Es 8X8, por lo que me tomó un tipo long y, por ejemplo, si quieres saber dónde están todas las piezas a bordo, tú or ambos jugadores.
Si desea todos los pasos posibles de un jugador, diga a la derecha - usted >> la representación de las piezas del jugador por uno, y AND con las piezas del oponente para verificar si ahora hay 1 comunes (eso significa que hay una pieza del oponente en su Correcto). Entonces sigues haciendo eso. Si vuelves a tus propias piezas, no te muevas. Si llegas a una parte clara, puedes moverte 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)

Answer 3

Aunque todo el mundo parece estar enganchado a las banderas, no es la única aplicación de los operadores de bit a bit (aunque probablemente la más común). Además, C # es un lenguaje de nivel suficientemente alto como para que otras técnicas 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 JIT de .NET probablemente lo hará por usted (y cualquier compilador decente de otro idioma), pero si realmente está preocupado por Cada microsegundo, puede 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 se quiere confundir a los inexpertos, como cuando se responde a una pregunta sobre la tarea. :)

Sin embargo, en cualquier código real, estará mucho mejor utilizando la multiplicación, ya que tiene una legibilidad mucho mejor y el JIT lo optimiza para shr y shr instrucciones de todos modos, por lo que no hay una penalización de rendimiento.

Unos cuantos trucos curiosos tratan con el operador ^ (XOR). Este es realmente un operador muy poderoso, debido a las siguientes propiedades:

• A^B == B^A
• A^B^A == B
• Si conoces A^B entonces es imposible saber qué son A y B , pero si conoces uno de ellos, puedes calcular el otro.
• El operador no sufre ningún desbordamiento como multiplicación / división / suma / resta.

Un par de trucos que he visto usando este operador:

Intercambiando 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 de doble enlace 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 mantengas un registro del puntero para el primer elemento; el puntero para el último elemento; y para cada ítem mantienes un registro de pointer_to_previous ^ pointer_to_next . De esta manera, puede recorrer la lista desde cualquiera de los extremos, pero la sobrecarga es solo la mitad de una lista enlazada tradicional. Aquí está el código de 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 desplazarse desde el final, solo necesita cambiar la primera línea de FirstItem a LastItem . Eso es otro ahorro de memoria allí mismo.

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

Answer 4

Cada vez que tiene una opción de 1 o más en combinación de elementos, entonces bitwise es generalmente una solución fácil.

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

Answer 5

Debería decir que uno de los usos más comunes es la modificación de los campos de bits para comprimir los datos. Principalmente ve esto en programas que intentan ser económicos con paquetes.

Ejemplo de compresión de red utilizando campos de bits.

Answer 6

Los usarás por varias razones:

• Almacenamiento (¡y comprobación!) de opciones de forma eficiente en memoria
• Si está haciendo programación computacional, puede considerar la optimización de algunas de sus operaciones mediante el uso de operaciones a nivel de bits 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 los demás.

Dicho esto, a veces hay que preguntarse: ¿vale la pena el esfuerzo por mejorar la memoria y el rendimiento? Después de escribir ese tipo de código, déjalo reposar un rato y vuelve a él. Si luchas con ello, reescribe con un código más mantenible.

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

Mejor aún, pídale a alguien que lo lea, y documente ampliamente.

Answer 7

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

Imagina que quieres escribir un solucionador de sudoku o simplemente un programa simple, que te muestre la pizarra y te permita resolver el rompecabezas por ti mismo, pero asegura que los movimientos son legales.

La placa en sí misma probablemente estará representada por una matriz bidimensional como:

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

El valor 0 significa 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 unos cuantos bucles, pero las máscaras de bits te permiten hacer las cosas mucho más rápido. En un programa simple que solo garantiza que las reglas se cumplan, 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 (el value es una uint ):

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

En la línea sobre 1u correspondiente al patrón de bits 00000000 00000000 00000000 00000001 se desplaza hacia la izquierda por el value - 1 . Si, por ejemplo, value == 5 , obtienes

00000000 00000000 00000000 00010000

Al principio, la máscara para cada fila, columna y cuadro es 0 . Cada vez que coloca un número en el tablero, 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 las 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áscara maskForNumbersSetInRow[3] tiene este aspecto:

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 utilizando bitwise u operator ( | ). Primero creas un patrón de bits correspondiente al valor 5

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

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

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

o usando una forma mas 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 hay algún valor en la fila, puede usar operator & para verificar si el bit correspondiente está establecido 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 apropiadas 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;

}

Teniendo las máscaras, puedes verificar si el movimiento 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);
}

Answer 8

Se pueden usar para una carga completa de diferentes aplicaciones, aquí hay una pregunta que he publicado aquí anteriormente, que utiliza operaciones bitwise:

Bitwise Y, Bitwise Inclusive OR pregunta, en Java

Para otros ejemplos, eche un vistazo a (por ejemplo) las enumeraciones marcadas.

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

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, está cubriendo todo.

HTH

Answer 9

Si alguna vez necesitas comunicarte con el hardware, necesitarás usar twiddling de bits en algún momento.

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

Muchas cosas

Answer 10

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

Answer 11

Una de las cosas más frecuentes en las que los uso en C # es producir códigos hash. Hay algunos métodos de hashing razonablemente buenos que los utilizan. Por ejemplo, para una clase coordinada con una X y una Y que fueran las dos iniciales que podría usar:

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

Esto genera rápidamente un número que se garantiza que es igual cuando se produce por un objeto igual (asumiendo que la igualdad significa que tanto los parámetros X como Y son los mismos en ambos objetos comparados) mientras que tampoco producen patrones de enfrentamiento para objetos de bajo valor (es probable que sean más común en la mayoría de las aplicaciones).

Otra es la combinación de enumeraciones de banderas. Por ejemplo, RegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase RegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase

Hay algunas operaciones de bajo nivel que generalmente no son necesarias cuando se codifica en un marco como .NET (por ejemplo, en C # No necesito 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.

Existen algunas técnicas de "twiddling" de bits, como redondear al número binario más cercano (p. Ej., Redondear 1010 a 10000):

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

Las cuales son útiles cuando las necesitas, pero eso no suele ser muy común.

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

Answer 12

Utilizo operadores bitwise para 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
}

Answer 13

Docenas de ejemplos de bits de bits aquí

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