Calculating an average.

A long standing bug in many algorithims is using the obvious


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)

Comments

  1. Hi Peter Lawrey,

    Thanks 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

    ReplyDelete

Post a Comment

Popular posts from this blog

Java is Very Fast, If You Don’t Create Many Objects

System wide unique nanosecond timestamps

Unusual Java: StackTrace Extends Throwable