這個計數器的魔法是如何工作的？

Question

雖然上工作XKCD愚人節skein hash collision problem我碰到這個strange, fast, multiplicative method跑了一個字計數位的設置：

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

爲什麼這個工作/這是怎麼回事？我們是否可以推廣這種方法（例如，爲了解決問題中的128位值）？

此外，我不禁想到它與這個問題有關moving bits around using a clever magic number。

Answer 1

這實際上並不計算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。

換言之，由於上述數學原因，模運算符有效地計算設置的最低有效位的數量 - 只要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的值。）

因此，我們已經將我們的副本15位數字在我們的64位寄存器中。第二步是掩碼只提取每個nybble的最低有效位。由於每個nybble的最低有效位等於1 (mod 15)，所以模運算符有效地計算nybbles中設置的最低有效位的數量。

剩下的唯一細節是確保我們的15位數字中的每一位都只出現在一個最不重要的位槽中一次。

讓我們來看看：

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's，而不是16.因此，位於最後一個nybble（從第60位開始，代表我們的值的第15位，即16位值的最高位）中的位被有效忽略。

就這樣，總的技術是完整的：

1. 用乘法來算，每比特映射到至少顯著半字節位。
2. 使用掩碼只選擇所需的nybble位。
3. 請注意，最不重要的位是1 (mod 15)。
4. 因此，(mod 15)將簡單地將這些位加在一起...最多設置14位。