java - 使用移位运算的除法近似如何工作？

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

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

变量length是大于或等于47的int。

我熟悉带符号的右移运算符的工作方式。但是我不知道为什么这些特定的运算会导致除以7。

最佳答案

>>是位移位的。您右移的每一位实际上就是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)

然后只需将无穷级数截断为所需的精度即可。