Home > Articles > Programming

This chapter is from the book

This chapter is from the book

2–5 Average of Two Integers

The following formula can be used to compute the average of two unsigned integers, ⌊(x + y)/2⌋ without causing overflow [Dietz]:

The formula below computes ⌈(x + y)/2⌉ for unsigned integers:

019equ01.jpg

To compute the same quantities (“floor and ceiling averages”) for signed integers, use the same formulas, but with the unsigned shift replaced with a signed shift.

For signed integers, one might also want the average with the division by 2 rounded toward 0. Computing this “truncated average” (without causing overflow) is a little more difficult. It can be done by computing the floor average and then correcting it. The correction is to add 1 if, arithmetically, x + y is negative and odd. But x + y is negative if and only if the result of (3), with the unsigned shift replaced with a signed shift, is negative. This leads to the following method (seven instructions on the basic RISC, after commoning the subexpression xy):

019equ02.jpg

Some common special cases can be done more efficiently. If x and y are signed integers and known to be nonnegative, then the average can be computed as simply 019fig01.jpg. The sum can overflow, but the overflow bit is retained in the register that holds the sum, so that the unsigned shift moves the overflow bit to the proper position and supplies a zero sign bit.

If x and y are unsigned integers and 019fig02.jpg, or if x and y are signed integers and xy (signed comparison), then the average is given by x + 019fig03.jpg. These are floor averages, for example, the average of −1 and 0 is −1.

  • + Share This
  • 🔖 Save To Your Account