Hacker's Delight

4-2. Propagating Bounds through Add’s and Subtract’s

Some optimizing compilers perform “range analysis” of expressions. This is the process of determining, for each occurrence of an expression in a program, upper and lower bounds on its value. Although this optimization is not a really big winner, it does permit improvements such as omitting the range check on a C “switch” statement and omitting some subscript bounds checks that compilers may provide as a debugging aid.

Suppose we have bounds on two variables x and y as follows, where all quantities are unsigned:

Equation 3

Then, how can we compute tight bounds on x + y, x − y, and −x? Arithmetically, ...