Можно ли переписать по модулю (2 ^ n - 1), используя побитовые и ограниченные операторы

Question

Для unsigned int x возможно ли вычислить x% 255 (или 2 ^ n - 1 в целом), используя только следующие операторы (плюс без цикла, вызова или вызова функции)?

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

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

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

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

РЕДАКТИРОВАТЬ 2:

Вот немного более оптимизированная версия в сочетании с условным кодом вычитания Пола Р.:

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

Answer 2

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

Answer 3

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

Но почему?

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