Java – how does this division approximation using displacement operations work?

In Java util. In dualpivotquicksort, the following line of code appears:

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

The variable length is an int greater than or equal to 47

I am familiar with how the shift right operator of a signature works But I don't know why these specific operations lead to an approximation of 7 Can anyone explain?

Solution

>>Is a bit shift Every bit you move to the right is actually divided by the number of 2

Therefore, (length > > 3) is length / 8 (rounded down), and (length > > 6) is length / 64

Take (length / 8) (length / 64) as about length * (1 / 8, 1 / 64) = length * 0.140625 (about)

1/7 = 0.142857 ……

For each item, the last 1 can be divided into 0.5, so length / 8 is rounded to the nearest (not down), and length / 64 is also rounded to the nearest

In general, you can easily approximate 1 / y, where y = 2 ^ n - 1, with a similar displacement approximation

The infinite geometry series is:

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

Multiply by X:

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

And substitute 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)

This is approximately y = 2 ^ n – 1

To approximate y = 2 ^ n 1, replace 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)

The infinite series is then truncated to the desired accuracy