c - 是否可以使用按位和受限运算符重写模 (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:

下面是结合了 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