### Calculating an average.

A long standing bug in many algorithims is using the obvious

The problem with this is that (h + l) can overflow for large values of h and l.

One alternative is a cumbersome

Or the one I prefer is using >>> to perform an unsigned divide by two

For example, say m, h and l where bytes and h = 100 and l = 90.

In the first case, h + l is -65 due to the overflow, so m = -32. (incorrect)

In the second case, h - l is 10, so m = 95 (correct)

In the last case, h + l is -65 or 10111110 in binary. Unsigned shifting right by 1 is 1011111 or 95. (correct)

int m = (h + l)/2;

The problem with this is that (h + l) can overflow for large values of h and l.

One alternative is a cumbersome

int m = l + (h - l)/2;

Or the one I prefer is using >>> to perform an unsigned divide by two

int m = (h + l) >>> 1;

For example, say m, h and l where bytes and h = 100 and l = 90.

In the first case, h + l is -65 due to the overflow, so m = -32. (incorrect)

In the second case, h - l is 10, so m = 95 (correct)

In the last case, h + l is -65 or 10111110 in binary. Unsigned shifting right by 1 is 1011111 or 95. (correct)

Hi Peter Lawrey,

ReplyDeleteThanks for the article, while grappling with content of this post I discovered the following things for myself

• l + (h - l)/2 uses 3 operations and (l + h) >>> 1 uses 2 operations

• (l + h) >>> 1 works only for positive numbers

• We cannot generalize this logic, eg: 4 numbers and unsigned right shift by 2 digits

-Mehar