JDK源碼DualPivotQuicksort類中利用移位求除7近似值？

在JDK8源碼中DualPivotQuicksort類中

// Inexpensive approximation of length / 7
int seventh = (length &>&> 3) + (length &>&> 6) + 1;

這種利用移位求除某個數的近似值是否有一定的公式或演算法，很是疑惑作者是如何想到這種思路？
(-100 &>&> 3) + (-100 &>&> 6) + 1 = -14
(100 &>&> 3) + (100 &>&> 6) + 1 = 14
(21 &>&> 3) + (21 &>&> 6) + 1 = 3


因為他們閱讀了一本書，名叫《Hacker"s Delight》，中文名叫《演算法心得：高效演算法的奧秘》，你問的問題出自第十章：除數為常量的整數除法，更具體點是第10.18: 不使用Multiply High指令的除法演算法。這本書就是位運算的黑魔法，你若喜歡，可以慢慢研讀。

思路大概是這樣的：

我們先只說正整數

我要把一個正整數n做除7運算，我認為除法太昂貴，我企圖用移位和加法來模擬這個除法。

通過移位，我只能完成2的整數倍的除法。

既然除7沒法完成，我先除個8吧。n/8 可以通過移位來完成。

可是我除8比除7得到的數要小，小多少呢？1/7-1/8=1/56。

換句話說，如果我可以完成 n/56，再配合上原來的 n/8，加在一起，就是 n/7 了。

可是 n/56 依然沒法完成，不過我可以完成一個和他很接近的 n/64。

這樣我的誤差就變成 n/448 了。

（這個過程可以一直進行下去，直到你對誤差滿意。原題的題目到這裡它就滿意了）

這是小學的思路，如果把它變成二進位，就是答案中已經有人給出的直接把1/7變成二進位的答案了。二者是一樣的，只是這個思路更適合沒有學過二進位的人。

這是演算法的思路，接下來是誤差分析。

首先演算法誤差已經給出了，是 n/448 。理論上在n比較小的時候，這個誤差應該是不太影響結果的。然而實際操作並非如此。因為我們還有系統誤差（計算誤差）。

我們知道，移位運算本身是會扔掉餘數的。

因此我們做的一切先移位，再加的運算，得到的結果是衡小於等於我們的理論結果的。每多一個移位項，我們的損失期望是0.5。換言之，由於有兩個移位項的存在（(n&>&>3)+(n&>&>6)），我們和真實結果的誤差大概是1。但這並不是公式在後面加1的理由。因為 n/7 本身的損失期望就是0.5（整數除法不四捨五入）！也就是說，對於正整數而言，在這裡加不加1，誤差是差不多的。大家可以去實驗一下，這裡加1隻稍優於不加（原因是我們的公式本身還有n/448的誤差）。

我們不妨在這裡稍作拓展，那在什麼情況下，這裡加1是真正有幫助的？我們理所當然地想到，既然每一個移位項引入0.5的誤差，而 n/7 本身損失期望是0.5，那我們引入三個移位項再加1，是不是就更接近結果了？

沒錯，如果我們的公式變成 (n&>&>3) + (n&>&>6) + (n&>&>9) + 1，即有三個移位項的情況下，這個加1帶來的收益會遠高於兩個移位項。有沒有加1的效果會變得更加清晰。大家可以試一下。

好，正整數差不多分析到這裡，接下來是負整數。

負整數有個最大的問題——移位並不等於除法。

在正整數中，n&>&>3 和 n/8 是完全等價的。而負整數不是。負整數用了神奇的補碼，所以 n&>&>3 並不再等於 n/8 。由於這個推導是稍顯複雜的，我們直接跳到結論——在負整數中，右移得到的結果，會向負取整，從而衡小於等於（絕對值大於等於）除法所得到的值。這時候每個移位項引入的和正確結果的誤差仍然是0.5，正確結果和整數除法結果的誤差也依然是0.5，但是方向反了！

因此在正整數中原本兩個移位項引入的和所求結果的0.5的系統誤差，到了負整數這裡，變成了1.5！也就是說，在引入了這個加1之後，正整數的系統誤差仍然是0.5，而負整數變成了0.5，從而降低了總體誤差。

回到我們的擴展，如果引入了第三項移位項，正整數的部分，系統誤差期望大概是0左右，而負整數的系統誤差期望是0.5*3+0.5-1=1。雖然正整數更準確了，但是負整數誤差更大了。何況還要引入額外的計算量。（當然，演算法誤差減小了，所以在n大的時候實際上肯定是更準確了）。

說的比較啰嗦，看得懂就看，看不懂就算了吧。

這種寫法被叫做OI綜合症，GitHub有個倉庫叫awesome bits，也有一堆位運算黑魔法。

有些演算法是和CPU指令執行效率相關的，多數已經過時。實際是否提高了效率還要實測為準，看看就好，權當了解一些不同的計算方法。