Hacker's Delight

4-3. Propagating Bounds through Logical Operations

As in the preceding section, suppose we have bounds on two variables x and y as follows, where all quantities are unsigned:

Equation 9

Then what are some reasonably tight bounds on x | y, x & y, x ⊕ y, and ¬x?

Combining inequalities (9) with some inequalities from Section 2-3 on page 16, and noting that ¬x = 2³² − 1 − x, yields

where it is assumed that the addition b + d does not overflow. These are easy to compute and might be good enough for the compiler application mentioned in the preceding ...