value range propagation for _bitwise_ OR

Don nospam at nospam.com
Sat Apr 10 13:17:30 PDT 2010


Rainer Deyke wrote:
> 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].
> 
> 

It's a very interesting puzzle. There are some pretty complex cases.

Consider (all numbers binary) a in [1010, 1100] and b in [101,101]. The 
maximum value is when a=1011, b=101, so max is 1111.



More information about the Digitalmars-d mailing list