algorithm - operadores - Bitwise y en lugar del operador de módulo

bitwise translate

Question

Sabemos que, por ejemplo, el módulo de potencia de dos se puede expresar así:

 x % 2 inpower n == x & (2 inpower n - 1).

Ejemplos:

x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7

¿Qué hay de la no potencia general de dos números?

Digamos:

x% 7 ==?

Answer 1

En este caso específico (mod 7), aún podemos reemplazar% 7 con operadores bit a bit:

// Return X%7 for X >= 0.
int mod7(int x)
{
while (x > 7) x = (x&7) + (x>>3);
return (x == 7)?0:x;
}

Funciona porque 8% 7 = 1. Obviamente, este código es probablemente menos eficiente que un simple x% 7, y ciertamente menos legible.

Answer 2

En primer lugar, no es exacto decir que

x % 2 == x & 1

Contraejemplo simple: x = -1 . En muchos idiomas, incluido Java, -1 % 2 == -1 . Es decir, % no es necesariamente la definición matemática tradicional de módulo. Java lo llama el "operador de resto", por ejemplo.

Con respecto a la optimización bit a bit, solo las potencias de módulo de dos se pueden "hacer fácilmente" en aritmética bit a bit. En términos generales, solo las potencias modulares de la base b se pueden hacer "fácilmente" con una representación de números base b .

En la base 10, por ejemplo, para N negativa, N mod 10^k solo está tomando los k dígitos menos significativos.

Referencias

• JLS 15.17.3 Operador remanente%
• Operación Wikipedia / Modulo

Answer 3

Este es específicamente un caso especial porque las computadoras representan números en la base 2. Esto es generalizable:

(número) _base % base ^x

es equivalente a los últimos x dígitos de la _base (número).

Answer 4

Esto solo funciona para poderes de dos (y con frecuencia solo positivos) porque tienen la propiedad única de tener solo un bit establecido en ''1'' en su representación binaria. Como ninguna otra clase de números comparte esta propiedad, no puede crear expresiones y bits para la mayoría de las expresiones de módulo.

Answer 5

Hay módulos distintos de potencias de 2 para los que existen algoritmos eficientes.

Por ejemplo, si x es 32 bits unsigned int entonces x% 3 = popcnt (x & 0x55555555) - popcnt (x & 0xaaaaaaaa)

Answer 6

No se usa el operador bit a bit ( & ) en binario, no lo hay. Boceto de la prueba:

Supongamos que hay un valor k tal que x & k == x % (k + 1) , pero k! = 2 ^ n - 1 . Entonces, si x == k , la expresión x & k parece "operar correctamente" y el resultado es k . Ahora, considere x == ki : si hubo algún "0" bits en k , hay algo i mayor que 0, que ki solo puede expresarse con 1 bits en esas posiciones. (Por ejemplo, 1011 (11) debe convertirse en 0111 (7) cuando 100 (4) ha sido restado de él, en este caso el 000 bit se convierte en 100 cuando i = 4. ) Si un bit de la expresión de k debe cambiar de cero a uno para representar ki , entonces no puede calcular correctamente x% (k + 1) , que en este caso debería ser ki , pero no hay forma de boolean a bit y producir ese valor dada la máscara.

Answer 7

Solo hay una forma simple de encontrar el módulo de 2 ^ i números usando bitwise.

Existe una forma ingeniosa de resolver casos de Mersenne según el enlace , como n% 3, n% 7 ... Existen casos especiales para n% 5, n% 255 y casos compuestos como n% 6.

Para los casos 2 ^ i, (2, 4, 8, 16 ...)

n % 2^i = n & (2^i - 1)

Los más complicados son difíciles de explicar. Lea solo si tiene mucha curiosidad.

Answer 8

Solo hay una forma simple de encontrar el módulo de 2 ^ i números usando bitwise.

Existe una forma ingeniosa de resolver casos de Mersenne según el enlace, como n% 3, n% 7 ... Existen casos especiales para n% 5, n% 255 y casos compuestos como n% 6.

Para los casos 2 ^ i, (2, 4, 8, 16 ...)

n% 2 ^ i = n & (2 ^ i - 1)

Los más complicados son difíciles de explicar. Lea solo si tiene mucha curiosidad.

@ Murali Cualquiera de estos métodos para n% [(2 ^ 16) +1] = 65537. Me refiero a n% (2 ^ k) +1 que es un primo.

Answer 9

Usando bitwise_and, bitwise_or, y bitwise_not puede modificar cualquier configuración de bit a otra configuración de bit (es decir, este conjunto de operadores está "funcionalmente completo"). Sin embargo, para operaciones como el módulo, la fórmula general sería necesariamente bastante complicada, ni siquiera me molestaría en intentar recrearla.

Answer 10

Módulo "7" sin operador "%"

int a = x % 7;
int a = (x + x / 7) & 7;