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

发布时间：2020-12-15 00:26:36 所属栏目：Java 来源：网络整理

导读：在 java.util.DualPivotQuicksort中,出现以下代码行： // Inexpensive approximation of length / 7int seventh = (length 3) + (length 6) + 1; 变量length是大于或等于47的int. 我熟悉签名的右移操作符的工作原理.但是我不知道为什么这些特定的操作会导致7

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

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

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

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

解决方法

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

因此,(长度>> 3)是长度/ 8(向下舍入),并且(长度>> 6)是长度/ 64.

取(长度/ 8)(长度/ 64)约为长度*(1/8 1/64)=长度* 0.140625(约)

1/7 = 0.142857 ……

对于每个项,最后的1可以被分成0.5,因此长度/ 8被舍入到最接近(而不是向下),并且长度/ 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)

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!