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