使用位操作并行计算模数

Question

以下链接是有点破解,显示如何平行计算模数2 ^ n - 1:ModulusDivisionParallel

你能解释这个位操作是如何工作的,以及如何在给定特定分母的情况下展开显示的循环(参见下面的例子,位掩码来自哪里)？

展开0xF循环的示例:

y = x mod 0xF
y = x & 0x0F0F0F0F + ((x & 0xF0F0F0F0) >> 4)  
y = y & 0x00FF00FF + ((y & 0xFF00FF00) >> 8)  
y = y & 0x0000FFFF + ((y & 0xFFFF0000) >> 16)  
y = y & 0xF

Answer 1

首先澄清一下：

当s = 4（即模数等于0xF）时，我得到以下展开：

m = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F)
m = ((n >> 16) + (n & 0x0000FFFF)
m = ((n >>  8) + (n & 0x000000FF)
m = ((n >>  4) + (n & 0x0000000F)
m = ((n >>  4) + (n & 0x0000000F)
m = ((n >>  4) + (n & 0x0000000F)
m = ((n >>  4) + (n & 0x0000000F)
m = m == 0xF ? 0 : m;

这与您的问题中的内容非常不同。解释一下为什么这样有效：

听说过这样的数学技巧：如果将一个数字的所有数字相加，并且该数字可以被 9 整除，那么原始数字也可以被 9 整除吗？这是可行的，因为原数和总和除以 9 的余数是相同的。实际上，这就是我们在这里所做的，只是使用不同的基数 - 在您的示例中，使用十六进制基数。

数学功夫是这样的：

每个十六进制数字对最终值的贡献可以表示为V * 16 ^ P。请注意16 ^ P = 1 (mod 15)，因此每个十六进制数字对最终值的贡献就是V (mod 15)。换句话说，要得到所有数字的总贡献，请将它们全部相加(mod 15)。

按位运算只是以对数步数执行此操作的一种巧妙方法：将十六进制数字的前半部分重复添加到后半部分。

9 技巧的问题是您最终可能会得到一个两位数：99 = 9 + 9 = 18 (mod 10)！然后你再重复一次：18 = 1 + 8 = 9 (mod 10)。

同样，我们进行“额外”迭代，m = ((n >> 4) + (n & 0x0000000F)直到剩余数字为一位数。

现在唯一剩下的细节是我们是否得到0xF我们想要的结果0x0。