9th May 2017, 4 min read

Signed integer division by a power of two can be expensive!

6 thoughts on “Signed integer division by a power of two can be expensive!”

1. Yoav says:
   May 9, 2017 at 5:05 pm

   Performance aside, the way you calculated middleIndex (both versions) is buggy (https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html).

   1. Daniel Lemire says:
      May 9, 2017 at 5:26 pm

      Sure, though if you have arrays spanning 4GB of memory, you probably have other problems to worry about.

   2. Arjen says:
      May 10, 2017 at 8:35 am

      That is a nice pointer, but the >>> should be right, actually!
      http://stackoverflow.com/a/19058871/2127435

   3. Konrad Borowski says:
      May 11, 2017 at 6:15 am

      The page you are linking even says that >>> 1 is one of methods to fix it.

2. Alessandro says:
   May 10, 2017 at 5:05 am

   Keep in mind that signed right shift are implementation dependent in C! (And signed left shifts are in general undefined). You should put in place compile time checks when using them.

3. lyrachord says:
   August 18, 2017 at 4:54 pm

   My benchmark result:
   # JMH version: 1.19
   # VM version: JDK 1.8.0_144, VM 25.144-b01
   # VM invoker: C:\work\JDK8\jre\bin\java.exe
   # VM options:

   Benchmark Mode Cnt Score Error Units
   IntBinarySearch.SequentialSearch thrpt 5 49816.892 ± 579.960 ops/s
   IntBinarySearch.branchlessBinarySearch thrpt 5 587342.727 ± 21659.254 ops/s
   IntBinarySearch.branchyBinarySearch thrpt 5 1000197.755 ± 40677.488 ops/s
   IntBinarySearch.branchyBinarySearchWithDivision thrpt 5 856292.173 ± 56034.160 ops/s
   IntBinarySearch.standardBinarySearch thrpt 5 1019794.676 ± 19766.743 ops/s