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

On sait par exemple que modulo de puissance de deux peut s’exprimer 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 à deux chiffres?

Disons:

x% 7 ==?

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

 x % 2 == x & 1 

Contre-exemple simple: x = -1 . Dans de nombreuses langues, y compris Java, -1 % 2 == -1 . C’est-à-dire que % n’est pas nécessairement la définition mathématique traditionnelle de modulo. Java l’appelle par exemple “l’opérateur restant”.

En ce qui concerne l’optimisation binary, seules les puissances modulo de deux peuvent être “facilement” effectuées dans l’arithmétique bit à bit. De manière générale, seules les puissances modulo de base b peuvent être “facilement” réalisées avec la représentation en base b des nombres.

Dans la base 10, par exemple, pour N non négatif, N mod 10^k prend juste les k chiffres les moins significatifs.

Les références

  • JLS 15.17.3 Opérateur restant%
  • Opération Wikipedia / Modulo

Il n’y a qu’un moyen simple de trouver modulo de 2 ^ numéros en utilisant bitwise.

Il existe un moyen ingénieux de résoudre les cas de Mersenne selon le lien tel que n% 3, n% 7 … Il existe des cas spéciaux 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 complexes sont difficiles à expliquer. Lisez seulement si vous êtes très curieux.

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

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

(nombre) base % base x

est équivalent aux x derniers chiffres de la base (nombre).

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

Par exemple, si x est 32 bits unsigned int alors x% 3 = popcnt (x & 0x55555555) – popcnt (x & 0xaaaaaaaa)

N’utilisant pas l’opérateur bitwise et ( & ) en binary, il n’y en a pas. Esquisse de la 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 & k semble “fonctionner correctement” et le résultat est k . Considérons maintenant x == ki : s’il y avait des bits “0” dans k , il y en a un plus grand que 0, ki ne pouvant être exprimé qu’avec 1-bit dans ces positions. (Par exemple, 1011 (11) doit devenir 0111 (7) lorsque 100 (4) en ont été soustraits. Dans ce cas, le bit 000 devient 100 lorsque i = 4. ) Si un bit de l’expression de k doit passer de zéro à l’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 de booléen au niveau du bit et de produire cette valeur étant donné le masque.

Modulo “7” sans opérateur “%”

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

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

 // 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 parce que 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 les configurations de bits en configurations de bits (c.-à-d. Que ces opérateurs sont “fonctionnellement complets”). Cependant, pour des opérations comme le module, la formule générale serait nécessairement assez compliquée, je ne prendrais même pas la peine de la recréer.

Il n’y a qu’un moyen simple de trouver modulo de 2 ^ numéros en utilisant bitwise.

Il existe un moyen ingénieux de résoudre les cas de Mersenne selon le lien tel que n% 3, n% 7 … Il existe des cas spéciaux 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 complexes sont difficiles à expliquer. Lisez seulement si vous êtes très curieux.

@ Murali Toutes ces méthodes pour n% [(2 ^ 16) +1] = 65537. Je veux dire n% (2 ^ k) +1 qui est un nombre premier.