Description Maxime Daniel 2007-05-24 02:03:24 EDT

Source based, circa v_764.
In several places, we use the following calculation to average two ints:
1) a + (b - a) / 2
(For example, Util#lineNumber or CodeStream#sort.)

The reason why we do not use the simpler:
2) (a + b) / 2
is that we want to avoid potential overflows.

I have made a few tests though that show that:
- 2) is about 20% faster than 1);
- an alternative implementation using >>>, 3) (a + b) >>> 1, is delivering the
  same results as 1) (for a and b positive or null, even when they approach
  Integer.MAX_VALUE), but is 25% *slower*;
- 4) (a + b) >> 1 is about 10% faster than 2).

I would thus suggest that we examine:
- whether we can live with a and b defined into [0, Integer.MAX_VALUE / 2[ or 
  not; if we can reduce the scope, then 4) would be the faster method to compute
  what we want;
- else document why we keep a slightly longer computation, and consider shifting
  to 5) a + (b - a) >> 1.

(Note: if I remember well, / 2 vs >> 1 speeds comparison varies from VM to VM,
which would probe for more investigation.)