Можно ли переписать modulo (2 ^ n - 1) с помощью побитовых и ограниченных операторов

Ответ 1

Да, это возможно. Для 255 это можно сделать следующим образом:

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

Это будет работать, если unsigned int - 32-разрядное целое число.

EDIT: шаблон должен быть достаточно очевиден, чтобы понять, как это можно обобщить на 2^n - 1. Вам просто нужно выяснить, сколько итераций необходимо. Для n = 8 и 32-битного целого числа должно быть достаточно 4 итераций.

ИЗМЕНИТЬ 2:

Здесь несколько более оптимизированная версия в сочетании с условным кодом вычитания 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

Ответ 2

Просто создайте массив со всеми значениями (нужно либо 32, либо 64 записи (т.е. 128 или 512 байт). Затем просто просмотрите.

Ответ 3

Конечно. Просто выйдите из своего старого учебника по компьютерной архитектуре и обновите свою память на булевой алгебре. CPU ALU делает это с AND и OR; вы тоже можете.

Но почему?

Академические упражнения? Домашнее задание? Любопытство?