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 section. The bounds in the first two inequalities, however, are not tight. For example, writing constants in binary, suppose

Equation 10

Then, by inspection (e.g., trying all 36 possibilities for x and y), we see that 01010 ≤ (x | y) ≤ 10111. Thus, the lower bound is not max(a, c) nor is it a | c, and the upper bound is not b + d, nor is it b | d.

Given the values of a, b, c, and d in inequalities (9), how can one obtain tight bounds on the logical expressions? Consider first the minimum value attained by x | y. A reasonable guess might be the value of this expression with x and y both at their minima—that is, a | c. Example (10), however, shows that the minimum can be lower than this.

To find the minimum, our procedure is to start with x = a and y = c, and then find an amount by which to increase either x or y so as to reduce the value of x | y. The result will be this reduced value. Rather than assigning a and c to x and y, however, we work directly with a and c, increasing one of them when doing so is valid and it reduces the value of a | c.

The procedure is to scan the bits of a and c from left to right. If both bits are 0, the result will have a 0 in that position. If both bits are 1, the result will have a 1 in that position (clearly, no values of x and y could make the result less). In these cases, continue the scan to the next bit position. If one scanned bit is 1 and the other is 0, then it is possible that changing the 0 to 1 and setting all the following bits in that bound’s value to 0 will reduce the value of a | c. This change will not increase the value of a | c, because the result has a 1 in that position anyway, from the other bound. Therefore, form the number with the 0 changed to 1 and subsequent bits changed to 0. If that is less than or equal to the corresponding upper limit, the change can be made; do it, and the result is the or of the modified value with the other lower bound. If the change cannot be made (because the altered value exceeds the corresponding upper bound), continue the scan to the next bit position.

That’s all there is to it. It might seem that after making the change, the scan should continue, looking for other opportunities to further reduce the value of a | c. However, even if a position is found that allows a 0 to be changed to 1, setting the subsequent bits to 0 does not reduce the value of a | c, because those bits are already 0.

C code for this algorithm is shown in Figure 4-3. We assume that the compiler will move the subexpressions ~a & c and a & ~c out of the loop. More significantly, if the number of leading zeros instruction is available, the program can be speeded up by initializing m with

m = 0x80000000 >> nlz(a ^ c); 

Figure 4-3. Minimum value of x | y with bounds on x and y.

unsigned minOR(unsigned a, unsigned b, 
               unsigned c, unsigned d) {
   unsigned m, temp; 

   m = 0x80000000; 
   while (m != 0) {
      if (~a & c & m) {
         temp = (a | m) & -m; 
         if (temp <= b) {a = temp; break;} 
      } 
      else if (a & ~c & m) {
         temp = (c | m) & -m; 
         if (temp <= d) {c = temp; break;} 
      } 
      m = m >> 1; 
   } 
   return a | c; 
} 

This skips over initial bit positions in which a and c are both 0 or both 1. For this speedup to be effective when a ^ c is 0 (that is, when a = c), the machine’s shift right instruction should be mod 64. If number of leading zeros is not available, it may be worthwhile to use some version of the flp2 function (see page 46) with argument a ^ c.

Now let us consider the maximum value attained by x | y, with the variables bounded as shown in inequalities (9). The algorithm is similar to that for the minimum, except it scans the values of bounds b and d (from left to right), looking for a position in which both bits are 1. If such a position is found, the algorithm tries to increase the value of c | d by decreasing one of the bounds by changing the 1 to 0, and setting all subsequent bits in that bound to 1. If this is acceptable (if the resulting value is greater than or equal to the corresponding lower bound), the change is made and the result is the value of c | d using the modified bound. If the change cannot be done, it is attempted on the other bound. If the change cannot be done to either bound, the scan continues. C code for this algorithm is shown in Figure 4-4. Here the subexpression b & d can be moved out of the loop, and the algorithm can be speeded up by initializing m with

mx = 0x80000000 >> nlz(b & d); 

Figure 4-4. Maximum value of x | y with bounds on x and y.

unsigned maxOR(unsigned a, unsigned b, 
               unsigned c, unsigned d) {
   unsigned m, temp; 

   m = 0x80000000; 
   while (m != 0) {
      if (b & d & m) {
         temp = (b - m) | (m - 1); 
         if (temp >= a) {b = temp; break;} 
         temp = (d - m) | (m - 1); 
         if (temp >= c) {d = temp; break;} 
      } 
      m = m >> 1; 
   } 
   return b | d; 
} 

There are two ways in which we might propagate the bounds of inequalities (9) through the expression x & y: algebraic and direct computation. The algebraic method uses DeMorgan’s rule:

Because we know how to propagate bounds precisely through or, and it is trivial to propagate them through not we have

For the direct computation method, the code is very similar to that for propagating bounds through or. It is shown in Figures 4-5 and 4-6. Figure 4-5. Minimum value of x & y with bounds on x and y.

unsigned minAND(unsigned a, unsigned b, 
                unsigned c, unsigned d) {
   unsigned m, temp; 

   m = 0x80000000; 
   while (m != 0) {
      if (~a & ~c & m) {
         temp = (a | m) & -m; 
         if (temp <= b) {a = temp; break;} 
         temp = (c | m) & -m; 
         if (temp <= d) {c = temp; break;} 
      } 
      m = m >> 1; 
   } 
   return a & c; 
} 

unsigned maxAND(unsigned a, unsigned b, 
                unsigned c, unsigned d) {
   unsigned m, temp; 

   m = 0x80000000; 
   while (m != 0) {
      if (b & ~d & m) {
         temp = (b & ~m) | (m - 1); 
         if (temp >= a) {b = temp; break;} 
      } 
      else if (~b & d & m) {
         temp = (d & ~m) | (m - 1); 
         if (temp >= c) {d = temp; break;} 
      } 
      m = m >> 1; 
   } 
   return b & d; 
} 

The algebraic method of finding bounds on expressions in terms of the functions for and, or, and not works for all the binary logical expressions except exclusive or and equivalence. The reason these two present a difficulty is that when expressed in terms of and, or, and not, there are two terms containing x and y. For example, we are to find

The two operands of the or cannot be separately minimized (without proof that it works, which actually it does) because we seek one value of x and one value of y that minimizes the whole or expression.

The following expressions may be used to propagate bounds through exclusive or:

It is straightforward to evaluate the minXOR and maxXOR functions by direct computation. The code for minXOR is the same as that for minOR (Figure 4-3) except with the two break statements removed, and the return value changed to a ^ c. The code for maxXOR is the same as that for maxOR (Figure 4-4) except with the four lines under the if clause replaced with

temp = (b - m) | (m - 1); 
if (temp >= a) b = temp; 
else {
   temp = (d - m) | (m - 1); 
   if (temp >= c) d = temp; 
} 

and the return value changed to b ^ d.

Signed Bounds

If the bounds are signed integers, propagating them through logical expressions is substantially more complicated. The calculation is irregular if 0 is within the range a to b, or c to d. One way to calculate the lower and upper bounds for the expression x | y is shown in Table 4-1. A “+” entry means that the bound at the top of the column is greater than or equal to 0, and a “-” entry means that it is less than 0. The column labelled “minOR (signed)” contains expressions for computing the lower bound of x | y and the last column contains expressions for computing the upper bound of x | y. One way to program this is to construct a value ranging from 0 to 15 from the sign bits of a, b, c, and d, and use a “switch” statement. Notice that not all values from 0 to 15 are used, because it is impossible to have a > b or c > d.

For signed numbers, the relation

holds, so the algebraic method can be used to extend the results of Table 4-1 to other logical expressions (except for exclusive or and equivalence). We leave this and similar extensions to others.