Re: value range propagation for _bitwise_ OR

[PBa]

Am 10.04.2010, 23:17 Uhr, schrieb Don <nos...@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;
}