这种使用位移操作的除法近似如何工作？

Question

在java.util.DualPivotQuicksort,出现以下代码行:

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

变量length是一个int大于或等于47.

我熟悉签名的右移操作符的工作原理.但是我不知道为什么这些特定的操作会导致7的近似值.有人可以解释一下吗？

Answer 1

>>是比特移位.你向右移动的每一位,实际上除以2的数量.

因此,(length >> 3)是length/8(向下舍入),(length >> 6)是length/64.

拿(length/8)+(length/64)约是length*(1/8+1/64)= length*0.140625(约)

1/7 = 0.142857...

所述+1在端部可被分成+0.5每个术语,以便length/8被舍入到最接近的(而不是向下),并且length/64也被四舍五入到最接近的.

通常,您可以轻松地近似1/y,y = 2^n+-1使用类似的位移近似.

无限几何系列是:

1 + x + x^2 + x^3 + ... = 1 / (1 - x)

乘以x:

x + x^2 + x^3 + ... = x/(1 - x)

而代替 x = 1/2^n

1/2^n + 1/2^2n + 1/2^3n + ... = (1/2^n) / (1 - 1/2^n)
1/2^n + 1/2^2n + 1/2^3n + ... = (1/2^n) / ((2^n - 1)/2^n)

1/2^n + 1/2^2n + 1/2^3n + ... = 1 / (2^n - 1)

这近似于y = 2^n - 1.

近似y = 2^n + 1,替代x = -1/2^n.

- 1/2^n + 1/2^2n - 1/2^3n + ... = (-1/2^n) / (1 + 1/2^n)
1/2^n - 1/2^2n + 1/2^3n - ... = (1/2^n) / ((2^n + 1)/2^n)

1/2^n - 1/2^2n + 1/2^3n - ... = 1 / (2^n + 1)

然后将无限级数截断为所需的精度.