value range propagation for _bitwise_ OR

[Rainer Deyke]

On 4/10/2010 11:52, Andrei Alexandrescu wrote:
> I think this would work:
> 
> uint maxOR(uint maxa, uint maxb) {
>     if (maxa < maxb) return maxOR(maxb, maxa);
>     uint candidate = 0;
>     foreach (i, bit; byBitDescending(maxa)) {
>         if (bit) continue;
>         auto t = candidate | (1 << (31 - i));
>         if (t <= maxb) candidate = t;
>     }
>     return maxa | candidate;
> }

This looks wrong.  Your function, if I understand it correctly, flips
all the bits in 'maxb' (excluding the leading zeros).  If 'maxb' is
exactly 1 less than a power of 2, then 'candidate' will be 0.  Now
consider a in [0, 16], b in [0, 15].  Your function will produce 16, but
the real maximum is 31.

For maximum accuracy, you have to consider the minima as well as the
maxima when calculating the new maximum.  With 'a' in [16, 16] and 'b'
in [16, 16], the new range can only be [16, 16].  With 'a' in [0, 16]
and 'b' in [0, 16], the correct new range is [0, 31].


-- 
Rainer Deyke - rainerd at eldwood.com