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

Question

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

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

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

我熟悉有符号右移操作符的工作方式。但我不知道为什么这些特定的操作会导致除以7的近似值。请有人解释一下吗？

- RCB

---

右移三位相当于进行了什么除法运算？ - Oliver Charlesworth

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)

然后将无限序列截断到所需的精度即可。

- ronalchn

---

我明白了。那么在末尾加1是为了“平衡”向下取整吗？ - RCB

是的，它会将长度除以8和长度除以64的一半相加，因此平均而言，它们会四舍五入到最近的数字，而不是向下取整。 - ronalchn

Answer 2

在众所周知的等式中，将x = 1/8代入：

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

并简化，以便提供。

1/8 + 1/64 + 1/512 + ...  = 1/7

将您的示例中的两边都乘以length，得到：

length / 7 = length / 8 + length / 64 + length / 512 + ...

请注意，这是“精确”除法，而不是整数除法 - 我在写数学，而不是Java代码。

然后，近似值假定第三个及以后的项对结果影响非常小，并且平均而言，length / 8和length / 64中的一个可能需要向上舍入，而不是向下舍入。因此，现在使用整数除法，length / 7 = length / 8 + length / 64 + 1是一个非常好的近似值。

你提供的表达式使用位运算符只是另一种编写方式，前提是length为正数。

- Dawood ibn Kareem

Answer 3

为了解释ronalchn的答案，我们需要一些数学背景知识：

由于7=8-1=8*(1-1/8)，因此通过等比数列除以7就相当于乘以

1/7 = 1/8·(1+1/8+1/8²+1/8³+…) = 1/8+1/8²+1/8³+…

同样地，如果要除以5，可以使用3·5=16-1，然后得到

1/5 = 3/16·(1+1/16+1/16²+…)

这个公式可以用来进行计算。

(3*n)<<4 + (3*n) << 8 + 1

- Lutz Lehmann

---

对于 1/5，乘法不一定便宜，因此更好的近似值可能是 1/4-1/16+1/64-1/256+...。 - ronalchn

是的，这可能更好，即使你需要更多的术语来描述它。编译器可以通过重复使用上次移位的值来优化这些连续的位移操作。 - Lutz Lehmann

Answer 4

计算所有值：

n/8 + n/64 - n/7

错误呈线性增长，同时保持负数。

下面的列表显示了给定错误第一次出现的时间。

n = 7 e = -1
n = 63 e = -2
n = 511 e = -3
n = 959 e = -4
n = 1407 e = -5
n = 1855 e = -6
n = 2303 e = -7
n = 2751 e = -8
n = 3199 e = -9
n = 3647 e = -10
n = 4095 e = -11
n = 4543 e = -12
n = 4991 e = -13
n = 5439 e = -14
n = 5887 e = -15
n = 6335 e = -16
n = 6783 e = -17
n = 7231 e = -18
n = 7679 e = -19
n = 8127 e = -20
n = 8575 e = -21
n = 9023 e = -22
n = 9471 e = -23
n = 9919 e = -24
...

这个比率显然趋近于1/448 = 1/8 + 1/64 - 1/7。

- user1196549