3

在处理 XKCD 愚人节的绞链散列冲突问题时，我遇到了这种奇怪的、快速的、乘法计算单词中设置位的方法：

c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

为什么这样做/发生了什么？我们能否推广这种方法（例如，从问题中处理我们的 128 位值）？

另外，我不禁认为这与这个关于使用聪明的幻数移动位的问题有关。

4

1 回答 1

3

实际上，这不计算 32 位字中的设置位，因为根据模运算符的性质，输出必须小于0xf（又名 15）。

首先，让我们特别注意模运算符。为什么是15？为什么我们要屏蔽每个 nybble 中的最低有效位？

好吧，请注意，每个最低有效 nybble 位都是16^ksome的值k。注意16 mod 15是 1，因此16^k mod 15对于 的任何非负整数值都是 1 k。

这很方便，因为它意味着16^k1 + 16^k2 + ... + 16^kn = n mod 15.

换句话说，由于上述数学运算，模运算符有效地计算了设置的最低有效 nybble 位的数量——只要 nybbles 中没有设置其他位。（他们只会碍事。）

但是，我们不想只计算 nybbles 中特殊格式的位。我们想计算任意值中设置的位数。诀窍是通过移动这些位将这些值位放入那些特殊格式化的 nybbles 中。nybbles 的最终顺序并不重要，只要我们可以将值的一位移动到一个 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 的最低有效位。因为每个 nybble 的最低有效位等效于1 (mod 15)模运算符有效地计算 nybbles 中设置的最低有效位的数量。

剩下的唯一细节是确保我们的 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 位值的最高位）被有效地忽略了。

这样，整个技术就完成了：

  1. 使用乘法将每个位映射到最低有效 nybble 位。
  2. 使用掩码仅选择所需的 nybble 位。
  3. 请注意，最低有效 nybble 位等价于1 (mod 15).
  4. 因此，(mod 15)只需将这些位相加……最多设置 14 位。
于 2013-04-08T17:49:15.760 回答