Operador bit a bit e no lugar do módulo

Sabemos que, por exemplo, o módulo de potência de dois pode ser expresso assim:

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

Exemplos:

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

E quanto ao não-poder geral de dois números?

Digamos:

x% 7 ==?

Em primeiro lugar, não é correto dizer que

x % 2 == x & 1

Contra-exemplo simples: x = -1. Em muitas linguagens, incluindo Java -1 % 2 == -1,. Ou seja, %não é necessariamente a definição matemática tradicional de módulo. Java o chama de "operador de resto", por exemplo.

Com relação à otimização bit a bit, apenas potências de módulo de dois podem "facilmente" ser feitas em aritmética bit a bit. De um modo geral, apenas potências de módulo de base b podem "facilmente" ser feitas com representação de números de base b .

Na base 10, por exemplo, para não negativos N, N mod 10^kfica apenas pegando os kdígitos menos significativos .

Referências

• JLS 15.17.3% restante do operador
• Operação Wikipedia / Módulo

Existe apenas uma maneira simples de encontrar o módulo de 2 ^ i números usando bit a bit.

Há uma maneira engenhosa de resolver os casos de Mersenne de acordo com o link , como n% 3, n% 7 ... Existem casos especiais para n% 5, n% 255 e casos compostos, como n% 6.

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

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

Os mais complicados são difíceis de explicar. Leia somente se você estiver muito curioso.

Isso só funciona para potências de dois (e freqüentemente apenas positivas) porque eles têm a propriedade única de ter apenas um bit definido como '1' em sua representação binária. Como nenhuma outra classe de números compartilha essa propriedade, você não pode criar expressões bit a bit para a maioria das expressões de módulo.

Este é especificamente um caso especial porque os computadores representam números na base 2. Isso é generalizável:

(número) _base % base ^x

é igual aos últimos x dígitos da _base (número) .

Existem módulos diferentes de potências de 2 para os quais existem algoritmos eficientes.

Por exemplo, se x tem 32 bits sem sinal int, então x% 3 = popcnt (x & 0x55555555) - popcnt (x & 0xaaaaaaaa)

Módulo "7" sem operador "%"

int a = x % 7;

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

Não usando o &operador bit a bit-and ( ) em binário, não há. Esboço da prova:

Suponha que houvesse um valor k tal que x & k == x % (k + 1), mas k! = 2 ^ n - 1 . Então, se x == k , a expressão x & kparece "operar corretamente" e o resultado é k . Agora, considere x == ki : se houvesse algum bit "0" em k , há algum i maior que 0, o qual ki só pode ser expresso com bits 1 nessas posições. (Por exemplo, 1011 (11) deve se tornar 0111 (7) quando 100 (4) foi subtraído dele, neste caso o bit 000 torna-se 100 quando i = 4. ) Se um bit da expressão de k deve mudar de zero para um para representar ki, então ele não pode calcular corretamente x% (k + 1) , que neste caso deveria ser ki , mas não há como o booleano bit a bit e produzir esse valor dada a máscara.

Neste caso específico (mod 7), ainda podemos substituir% 7 por 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, esse código é provavelmente menos eficiente do que um simples x% 7 e, certamente, menos legível.

Usando bitwise_and, bitwise_or e bitwise_not você pode modificar qualquer configuração de bit para outras configurações de bit (isto é, este conjunto de operadores é "funcionalmente completo"). Porém, para operações como módulo, a fórmula geral seria necessariamente muito complicada, eu nem me daria ao trabalho de tentar recriá-la.