value range propagation for _bitwise_ OR

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Sat Apr 10 14:05:06 PDT 2010


On 04/10/2010 01:55 PM, 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).

It tries to set all bits in which maxa is zero starting and keeps them 
set if the resulting number is less than maxb.

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

If maxb is 2^^N-1, then it will fill all nonzero bits of maxa.

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

The minimum for unsigned numbers is very simple: min(mina, minb).


Andrei



More information about the Digitalmars-d mailing list