value range propagation for logical OR

[Adam D. Ruppe]

On Sat, Apr 10, 2010 at 12:01:45PM -0500, Andrei Alexandrescu wrote:
> byte c = a | b;
> 
> Say you already know min_a, max_a, min_b, and max_b. How do you compute 
> min_c and max_c? I thought of it for a bit and it seems quite tricky.

min_c seems easy enough:
min_c = max(min_a, min_b);

When you or two values together, the result must be >= both of them, and this
does the trick there.

max_c is a bit harder. The obvious solution of:

max_c = max(max_a, max_b);

Fails because of 0b1100 | 0b0011... looking at this example, let's try:

max_c = max_a + max_b;

It covers that case, but is too big for 0b1111 | 0b1111.

This might work:

int numbits(number) { return the number of bits required to hold that number; }

if ( numbits(max_a + max_b) > max(numbits(max_a), numbits(max_b)) )
    max_c = 2 ^^ (max(numbits(max_a), numbits(max_b))) - 1;
else
    max_c = max_a + max_b;


The biggest we can possibly get is the sum of the two numbers. But, if it carries
over to more bits than either option, we truncate it - OR never gives more bits
than the two arguments. So we assume the max is the worst case of all ones or'd
with all ones.

I think this would work, but might not be the best we can possibly do. It is the
best I can think of though.

-- 
Adam D. Ruppe
http://arsdnet.net