value range propagation for _bitwise_ OR

[Andrei Alexandrescu]

(By the way I meant _bitwise_ in the title.)

On 04/10/2010 12:38 PM, Adam D. Ruppe wrote:
> 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.

Yah, that works for unsigned types. For signed types, it's tricky (as 
tricky as max).

> 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.

Yah, sum is a bound for max, but not the exact max. This is because 
bitwise OR is like a sum without transport.

> 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.

Even on the branch that doesn't use the sum, that's still just a bound. 
Consider:

a = 8;
b = 4;

Then max(a|b) is 12, but computed with your method is 15.


Andrei