Bitwise et à la place de l'opérateur de module

Nous savons que par exemple modulo de puissance de deux peut être exprimé comme ceci:

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

Exemples:

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

Qu'en est-il de la non-puissance générale de deux nombres?

Disons:

x% 7 ==?

Tout d'abord, il n'est pas exact de dire que

x % 2 == x & 1

Simple contre - : x = -1. Dans de nombreuses langues, y compris Java, -1 % 2 == -1. Autrement dit, %n'est pas nécessairement la définition mathématique traditionnelle de modulo. Java l'appelle par exemple "opérateur de reste".

En ce qui concerne l'optimisation au niveau du bit, seules les puissances modulo de deux peuvent "facilement" être effectuées en arithmétique au niveau du bit. D'une manière générale, seules les puissances modulo de base b peuvent "facilement" être réalisées avec une représentation en base b des nombres.

En base 10, par exemple, pour non-négatif N, N mod 10^kprend juste les kchiffres les moins significatifs .

Références

• JLS 15.17.3 Opérateur restant%
• Wikipédia / Fonctionnement Modulo

Il n'y a qu'un moyen simple de trouver un module de 2 ^ i nombres en utilisant le bit.

Il existe une manière ingénieuse de résoudre les cas de Mersenne selon le lien tel que n% 3, n% 7 ... Il existe des cas particuliers pour n% 5, n% 255 et des cas composites tels que n% 6.

Pour les cas 2 ^ i, (2, 4, 8, 16 ...)

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

Les plus compliqués sont difficiles à expliquer. Ne lisez que si vous êtes très curieux.

Cela ne fonctionne que pour les puissances de deux (et souvent uniquement positives) car elles ont la propriété unique de n'avoir qu'un seul bit mis à «1» dans leur représentation binaire. Étant donné qu'aucune autre classe de nombres ne partage cette propriété, vous ne pouvez pas créer d'expressions et de bits pour la plupart des expressions de module.

C'est spécifiquement un cas particulier car les ordinateurs représentent des nombres en base 2. Ceci est généralisable:

(nombre) _base % base ^x

équivaut aux x derniers chiffres de la _base (nombre) .

Il existe des modules autres que les puissances de 2 pour lesquels des algorithmes efficaces existent.

Par exemple, si x est 32 bits non signé int alors x% 3 = popcnt (x & 0x55555555) - popcnt (x & 0xaaaaaaaa)

Modulo "7" sans opérateur "%"

int a = x % 7;

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

Ne pas utiliser l' &opérateur binaire et ( ) en binaire, il n'y en a pas. Esquisse de preuve:

Supposons qu'il y ait une valeur k telle que x & k == x % (k + 1), mais k! = 2 ^ n - 1 . Alors si x == k , l'expression x & ksemble "fonctionner correctement" et le résultat est k . Maintenant, considérons x == ki : s'il y avait des bits "0" dans k , il y a un certain i supérieur à 0 qui ki ne peut être exprimé qu'avec 1 bits dans ces positions. (Par exemple, 1011 (11) doit devenir 0111 (7) lorsque 100 (4) en a été soustrait, dans ce cas, le bit 000 devient 100 lorsque i = 4. ) Si un bit de l'expression de k doit changer de zéro à un pour représenter ki, alors il ne peut pas calculer correctement x% (k + 1) , qui dans ce cas devrait être ki , mais il n'y a aucun moyen pour le booléen au niveau du bit et de produire cette valeur étant donné le masque.

Dans ce cas précis (mod 7), nous pouvons toujours remplacer% 7 par des opérateurs bit à bit:

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

Cela fonctionne car 8% 7 = 1. Evidemment, ce code est probablement moins efficace qu'un simple x% 7, et certainement moins lisible.

En utilisant bitwise_and, bitwise_or et bitwise_not, vous pouvez modifier n'importe quelle configuration de bit en une autre configuration de bit (c'est-à-dire que cet ensemble d'opérateurs est "fonctionnellement complet"). Cependant, pour des opérations comme le module, la formule générale serait forcément assez compliquée, je ne prendrais même pas la peine d'essayer de la recréer.