整數除以7

Question

源我的答案：

Is this expression correct in C preprocessor

我一點點我的長處在這裏，我試圖理解這個特定的優化工作。

正如答覆中提到，GCC將通過7優化整數除法：

mov edx, -1840700269 
mov eax, edi 
imul edx 
lea eax, [rdx+rdi] 
sar eax, 2 
sar edi, 31 
sub eax, edi 

它轉換回C作爲：

int32_t divideBySeven(int32_t num) { 
    int32_t temp = ((int64_t)num * -015555555555) >> 32; 
    temp = (temp + num) >> 2; 
    return (temp - (num >> 31)); 
} 

讓我們先來看看第一部分：

int32_t temp = ((int64_t)num * -015555555555) >> 32; 

爲什麼這個數字？

那麼，讓我們取2^64併除以7，看看彈出了什麼。

2^64/7 = 2635249153387078802.28571428571428571429 

這看起來像一團糟，如果我們把它轉換成八進制呢？

0222222222222222222222.22222222222222222222222 

這是一個非常漂亮的重複模式，肯定不能是巧合。我的意思是我們記得7是0b111，我們知道當我們除以99時，我們傾向於獲得基數爲10的重複模式。因此，當我們除以7時，我們將在基數8中得到重複模式。

那麼我們的號碼進來了嗎？

(int32_t)-1840700269相同(uint_32t)2454267027

* 7 = 17179869189

最後17179869184是2^34

這意味着17179869189爲7 2^34最接近的倍數。或者換一種說法2454267027是，將適合在uint32_t，當乘以7非常接近的2

什麼是八進制這個數字電源數量最多？

0222222222223 

爲什麼這很重要？那麼，我們要除以7.這個數字大約是2^34/7 ...。所以如果我們乘以它，然後移位34次，我們應該得到一個非常接近確切數字的數字。

最後兩行看起來像是爲修補近似誤差而設計的。

也許有人在這方面有更多的知識和/或專業知識可以在這方面作出貢獻。

>>> magic = 2454267027 
>>> def div7(a): 
... if (int(magic * a >> 34) != a // 7): 
...  return 0 
... return 1 
... 
>>> for a in xrange(2**31, 2**32): 
... if (not div7(a)): 
...  print "%s fails" % a 
... 

故障開始在3435973841這是有趣的是0b11001100110011001100110011010001

判斷爲什麼逼近失敗是有點超出我，爲什麼補丁修復它是爲好。有誰知道魔法如何超越我在這裏放下的東西？

Answer 1

該算法的第一部分由一個近似乘以7.倒數在這種情況下，我們計算近似與整數乘法和右位移位的倒數。

首先，我們看到值-1840700269（八進制-015555555555）爲32位整數。如果您將其讀取爲無符號的32位整數，則其值爲2454267027（八進制22222222223）。事實證明，2454267027/2^34與1/7非常接近。

爲什麼我們選擇這個號碼的2這個特殊的權力？我們使用的整數越大，近似值越接近。在這種情況下，2454267027似乎是最大的整數（滿足上述屬性），您可以使用該整數乘以帶符號的32位整數，而不會溢出64位整數。接下來，如果我們立即右移>> 34並將結果存儲在32位int中，我們將失去兩個最低位的精度。這些位對於確定整數除法的正確底數是必需的。

我不知道第二行是從x86代碼翻譯正確。在這一點上，temp大約爲num * 4/7，所以num * 4/7 + num到和位移是想給你約num * 1/7 + num * 1/4，一個相當大的誤差。

例如，作爲輸入57，在那裏57 // 7 = 8。我在代碼驗證下面還有：

• 57 * 2454267027 = 139893220539
• 139893220539 >> 32 = 32（在這一點上約57 * 4/7 = 32.5714...）
• 32 + 57 = 89
• 89 >> 2 = 22
（呵呵??無處接近 8在這一點上。）

反正最後一行，這是我們計算符號整數除法這種方式後進行調整。筆者從部分引用來自黑客的喜悅簽署師：

代碼最自然的計算樓層劃分結果，所以我們需要 修正，使其計算傳統的朝0 結果截斷。如果股息爲負數，則可以通過 三條計算指令加上股息來完成此操作。

在這種情況下（指你的其他文章）似乎是在做簽署的轉變，所以它會在負數的情況下，減去-1;給出+1的結果。

這甚至不是你所能做到的;這裏有一個更瘋狂的blog post about how to divide by 7 with just a single multiplication。