在处理XKCD的愚人节串散列冲突问题时，我偶然发现了一种奇怪的、快速的、乘法的方法来计算单词中的集合位:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
为什么这个工作/发生了什么?我们是否可以推广这种方法(例如，从问题中提取128位值)?
同时，我忍不住认为这与使用一个巧妙的幻数来移动比特的问题有关。
实际上，这并不计算32位字中的集合位，因为根据模运算符的性质，输出必须小于0xf(也就是15)。
首先，让我们特别注意模算子。为什么15 ?为什么我们要在每个点上都掩码到最低有效位呢?
请注意，对于某些k，每个最低有效位都是16^k的值。注意16 mod 15是1，因此16^k mod 15对于k的任何非负整数值都是1。
这很方便，因为它意味着16^k1 + 16^k2 + ... + 16^kn = n mod 15 .
换句话说，模运算符有效地计算了由于上述数学计算而设置的最不重要的尼布尔位的数量——只要尼布尔中没有设置其他位。(他们只会碍事。)
然而，我们不希望在字节中只计算特殊格式的位。我们想要计算任意值中设置的位数。诀窍是通过移动这些位来将这些值位转换为特殊格式的字节。nybble的最终顺序并不重要，只要我们可以将值的一位移动到一个nybble即可。理论上，由于我们使用64位值进行计数，我们可以将16位值中的每个位映射到它自己的nybble，从而得到4 * 16 = 64位的总数，正好在64位允许范围内。但是，请注意，因为我们使用的是模15，所以任何有15或16个设置位的值将分别显示为0或1。
现在让我们重新关注这个奇怪的常数:0x200040008001ULL
让我们注意设置了哪些位(其中0位是最低有效位):0、15、30和45。你可能已经注意到它们以15位为间隔。这很方便，因为对于小于2^15的值，这种乘法只是在64位字中创建值的多个移位副本。但是当值大于或等于2^15时，副本开始叠加，这对于计算比特不再有用。不过，这没关系，因为通过模运算，我们甚至不能可靠地计数到15位的信息。(然而，如果模运算的结果为0，我们知道所有位都被设置或没有被设置，同样假设我们只得到小于2^15的值。)
因此，我们在64位寄存器中移位了15位数的拷贝。第二步是掩模只提取每个nybble的最低有效位。因为每个尼布尔的最低有效位相当于1 (mod 15)，模运算符有效地计数尼布尔中设置的最低有效位的数量。
剩下的唯一细节是确保我们的15位数字中的每个位正好一次落在最不有效的nybble位槽中。
让我们检查:
The first bit set, 0, doesn't shift the value at all, giving our value bits 0 through 14.
This places value value bits 0, 4, 8, and 12 in a least significant nybble bit slot.
The second bit set, 15, gives our value bits 15 through 29.
This places our value bits 1, 5, 9, and 13 in bits 16, 20, 24, and 28.
The third bit set, 30, gives our value bits 30 through 44.
This places our value bits 2, 6, 10, and 14 in bits 32, 36, 40, and 44.
Finally, the forth bit set, 45, gives our value bits 45 through 59.
This places our value bits 3, 7, 11, and 15 in bits 48, 52, 56, and 60.
Bits accounted for:
0, 4, 8, and 12
1, 5, 9, and 13
2, 6, 10, and 14
3, 7, 11, and 15
很容易直观地验证这映射为16位。但是，请注意掩码实际上是15个1，而不是16个。因此，放置在最后一个nybble中的位(从第60位开始，代表我们值的第15位，16位值的最高位)被有效地忽略。
这样，整个技术就完成了:
- 使用乘法将每个位映射为最低有效位。
- 使用掩码只选择所需的nybble位
- 注意，最低有效位相当于
1 (mod 15)。 因此，
(mod 15)将简单地将这些位加在一起…