在不使用模算子的情况下，有没有有效的多对一算法？

Question

给定一个包含1~N的集合，并且我尝试公平地将它们映射到M个槽(N > M)中。我认为这是多对一的映射问题。

简单的解决方案是使用模运算符，给定N= 10和M= 3，我们可以进行如下映射：

N   M

1 % 3 = 1 (assign to 2nd slot)
2 % 3 = 2 (assign to 3rd slot)

...

9 % 3 = 0 (assign to 1st slot)

这一解决方案似乎相当公平，但需要昂贵的运营商。有没有现有的算法来解决这类问题？

提前感谢！

Answer 1

如果%是一个缓慢的运算符，这是有争议的，但是位操作更快。如果您很乐意映射到多个二次方( M=2^k )的回收箱中，那么您就可以屏蔽较低的k位。

x & (M - 1);

或

x & ((1 << k)-1);

如果回收箱的数目是Mersenne素数，M= 2^s-1，那么也有一种快速的方法可以得到剩余的部分：

unsigned int mod_Mersenne(unsigned int x, unsigned int s)
{
     unsigned int p = (1 << s) - 1;
     unsigned int y = (x & p) + (x >> s);
     return (y > p) ? y - p : y;
}

我相信你也能做到，但我不记得是怎么做的。

如果您需要按顺序存放数字，如您的示例中所示，如果您可以选择M作为较小整数的单词大小，您还可以利用这些无符号整数类型处理溢出，就像模一样，所以您可以这样做

unsigned char i = 0; // M = 256 (probably)
for (int j = 0; j < N; j++, i++)
    bin[i]++; // do something with the bin

当i超过无符号字符的大小时，它将被包装为零。

这是保证只有无符号，所以这里不要使用有符号整数。而且要注意，一个字符不一定是八位，但是你可以检查。(很有可能)。

通常，无符号算术的行为就好像您已经使用了模，所以如果您可以选择N来匹配一个字大小，就可以利用它。

Answer 2

具有常数m = n % M的模数M通常直接从定义中实现。

m = n - M*(n/M)

这很容易被认为是昂贵的-至少与比特掩蔽相比。

对于由常量、复杂的编译器进行除法，通常会实现另一种算法(由Montgomery开发)，该算法首先包含一个倒数乘法近似，然后一个或两个调整阶段来修正某些角情况，其中第一个近似m' = (n * R) >> K)可以被一个(或两个)舍弃。

这表明了一些改进：

range.

• considering

• 小心地跳过了调整阶段，用一些值抵消了(1<<k)/M，这样如果映射函数实际上需要模数，那么新系数0 <= m'' = (n * R) >> K < M的乘积的顶部位完全在所需的内:如果0<= m'' < M足够了，就不需要乘以0<= m'' < M了。

对于N=10，M=3，比较合适的系数是K=256/3 = 85，k= 8，它将n=0..9的值映射为m=0..2，m = n * 85 >> 8为

//  n = 0 1 2 3 4 5 6 7 8 9
//  m = 0 0 0 0 1 1 1 2 2 2   (approximation of n/3)

(得到相同输出值集的最小数是btw K=16/3 = 5，k= 4)。