value range propagation for _bitwise_ OR

[PBa]

Am 10.04.2010, 23:17 Uhr, schrieb Don <nospam at nospam.com>:

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


How about this?

import std.stdio, std.conv, std.intrinsic;

void main(string[] args)
{
   int total = 0, match = 0, from = to!(int)(args[1]), to =  
to!(int)(args[2]);
   uint res, resBF;
   for(int i = from; i < to; ++i)
   {
     for(int j = i; j < to; ++j)
     {
       for(int k = from; k < to; ++k)
       {
         for(int m = k; m < to; ++m)
         {
           ++total;
           res = maxOr(i, j, k, m);
           resBF = maxOrBF(i, j, k, m);
           if(res == resBF) ++match;
           //else writefln("mismatch: minA %s, maxA %s, minB %s, maxB %s,  
maxOr %s, maxOrBF %s", i, j, k, m, res, resBF);
         }
       }
     }
   }
   writefln("total %s, match %s", total, match);
}

uint max(uint a, uint b)
{
   return (a > b) ? a : b;
}

uint maxOr(uint minA, uint maxA, uint minB, uint maxB)
{
   uint result = minA | maxA | minB | maxB,
     diff = max(maxA - minA, maxB - minB);

   if(diff)
   {
     result |= (1 << (bsr(diff) + 1)) - 1;
   }
   return result;
}

/* compute result using brute force */
uint maxOrBF(uint minA, uint maxA, uint minB, uint maxB)
{
   return bitsSetInIntervallBF(minA, maxA) | bitsSetInIntervallBF(minB,  
maxB);
}

uint bitsSetInIntervallBF(uint min, uint max)
{
   uint result = 0;

   for(; min <= max; ++min)
   {
     result |= min;
   }
   return result;
}