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

Question

Nous savons que, par exemple, le modulo d'une puissance de deux peut être exprimé de la manière suivante :

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== ?

Answer 1

Tout d'abord, il est en fait inexact de dire que

x % 2 == x & 1

Contre-exemple simple : x = -1 . Dans de nombreux langages, y compris Java, -1 % 2 == -1 . C'est-à-dire, % n'est pas nécessairement la définition mathématique traditionnelle de modulo. Java l'appelle "opérateur de reste", par exemple.

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

En base 10, par exemple, pour les valeurs non négatives. N , N mod 10^k c'est juste prendre le moins significatif k les chiffres.

Références

• JLS 15.17.3 Opérateur de reste %
• Wikipedia/Modulo Operation

Answer 2

Cela ne fonctionne que pour les puissances de deux (et souvent uniquement pour les positives) car elles ont la propriété unique de n'avoir qu'un seul bit à "1" dans leur représentation binaire. Comme aucune autre classe de nombres ne partage cette propriété, il est impossible de créer des expressions de type bit-and pour la plupart des expressions de modulus.

Answer 3

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

(nombre) _base % de base x

est égal aux x derniers chiffres de (nombre) _base .

Answer 4

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

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

Answer 5

Modulo "7" sans opérateur "%".

int a = x % 7;

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