Bit a bit y en lugar de operador de módulo

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é pasa con el no poder general de dos números?

Digamos:

x% 7 ==?

Primero que nada, en realidad no es exacto decir que

x % 2 == x & 1

Contraejemplo simple: x = -1. En muchos lenguajes, como 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, en aritmética bit a bit sólo se pueden realizar "fácilmente" potencias de módulo de dos. En términos generales, sólo las potencias de módulo de base b se pueden hacer "fácilmente" con la representación de números en base b .

En base 10, por ejemplo, para no negativo N, N mod 10^ksolo se toman los kdígitos menos significativos .

Referencias

• JLS 15.17.3% de operador restante
• Operación Wikipedia / Modulo

Solo hay una forma sencilla de encontrar el módulo de 2 ^ i números utilizando bit a bit.

Hay una manera ingeniosa de resolver los casos de Mersenne según el enlace , como n% 3, n% 7 ... Hay 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.

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

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

(número) _base % base ^x

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

Hay módulos distintos de las 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)

Módulo "7" sin operador "%"

int a = x % 7;

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

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

Suponga 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 & kparece "operar correctamente" y el resultado es k . Ahora, considere x == ki : si hubiera bits "0" en k , hay algo de i mayor que 0, el cual ki solo puede expresarse con bits 1 en esas posiciones. (Por ejemplo, 1011 (11) debe convertirse en 0111 (7) cuando se le ha restado 100 (4), en este caso el bit 000 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 bit a bit booleano y producir ese valor dada la máscara.

En este caso específico (mod 7), todavía 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.

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 módulo, la fórmula general sería necesariamente bastante complicada, ni siquiera me molestaría en intentar recrearla.