How does this approximation of division using bit shift operations work?

Question

In java.util.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 signed right shift operator works. But I do not know why these particular operations result in an approximation of division by 7. Could someone explain please?

Answer 1

>> is bitshift. Every bit you shift right, in effect divides the number of 2.

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

Take (length/8)+(length/64) is approximately length*(1/8+1/64) = length*0.140625 (approximately)

1/7 = 0.142857...

The +1 at the end can be split into +0.5 for each term, so that length/8 is rounded to nearest (instead of down), and length/64 is also rounded to nearest.

---

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

The infinite geometric series is:

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

Multiplying by x:

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

And substituting 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 approximates y = 2^n - 1.

To approximate y = 2^n + 1, substitute x = -1/2^n instead.

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

Then just truncate the infinite series to the desired accuracy.

Answer 2

Set x = 1/8 in the well-known equality

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

and simplify, to give

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

Multiply both sides of this by length in your example, to give

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

Note that this is "exact" division, not integer division - I'm writing mathematics, not Java code.

Then the approximation assumes that the third and subsequent terms will be too small to matter, and that on average one of length / 8 and length / 64 is likely to need rounding up, rather than rounding down. So, now using integer division, length / 7 = length / 8 + length / 64 + 1 is a very good approximation.

The expression you gave, using bitwise operators, is just an alternative way of writing this, provided length is positive.