Est-il possible de réécrire modulo (2 ^ n – 1) en utilisant des opérateurs au niveau du bit et restreint

Pour unsigned int x, est-il possible de calculer x% 255 (ou 2 ^ n – 1 en général) en utilisant uniquement les opérateurs suivants (plus aucun appel de boucle, de twig ou de fonction)?

! , ~ , & , ^ , | , + , << , >> .

Oui c’est possible. Pour 255, cela peut être fait comme suit:

 unsigned int x = 4023156861; x = (x & 255) + (x >> 8); x = (x & 255) + (x >> 8); x = (x & 255) + (x >> 8); x = (x & 255) + (x >> 8); // At this point, x will be in the range: 0 <= x < 256. // If the answer 0, x could potentially be 255 which is not fully reduced. // Here's an ugly way of implementing: if (x == 255) x -= 255; // (See comments for a simpler version by Paul R.) unsigned int t = (x + 1) >> 8; t = !t + 0xffffffff; t &= 255; x += ~t + 1; // x = 186 

Cela fonctionnera si unsigned int est un entier de 32 bits.

EDIT: Le motif devrait être assez évident pour voir comment cela peut être généralisé à 2^n - 1 . Vous devez juste déterminer combien d’itérations sont nécessaires. Pour n = 8 et un entier de 32 bits, 4 itérations devraient suffire.

EDIT 2:

Voici une version légèrement plus optimisée combinée avec le code de soustraction conditionnelle de Paul R.:

 unsigned int x = 4023156861; x = (x & 65535) + (x >> 16); // Reduce to 17 bits x = (x & 255) + (x >> 8); // Reduce to 9 bits x = (x & 255) + (x >> 8); // Reduce to 8 bits x = (x + ((x + 1) >> 8)) & 255; // Reduce to < 255 

Créez simplement un tableau avec toutes les valeurs (vous avez seulement besoin de 32 ou 64 entrées (soit 128 ou 512 octets). Ensuite, faites une recherche.

Sûr. Sortez simplement l’un de vos anciens manuels d’architecture informatique et rafraîchissez votre mémoire sur l’algèbre booléenne. L’ALU d’une unité centrale le fait avec des ET et des OU; vous pouvez également.

Mais pourquoi?

Un exercice académique? Devoirs? La curiosité?