value range propagation for _bitwise_ OR

[Rainer Deyke]

On 4/11/2010 11:16, Ali Çehreli wrote:
> Rainer Deyke wrote:
>> How about this?
>>
>> uint fill_bits(uint min_v, uint max_v) {
>>   uint mask = 0;
>>   for (int i = 0; i < 32; ++i) {
>>     if ((min_v | (1 << i)) <= max_v) mask |= (1 << i);
>>   }
>>   return mask;
>> }
>>
>> max_c = min(
>>   max_a | fill_bits(min_b, max_b),
>>   max_b | fill_bits(min_a, max_a));
>>
>>
> 
> That proposal looks at the two pairs of a and b separately. For example,
> works with min_a and max_a, and decides a bit pattern.
> 
> What if the allowable bit pattern for the b pair has 0 bits that would
> be filled with an value of a that was missed by fill_bits for a? Imagine
> a value of a, that has little number of 1 bits, but one of those bits
> happen to be the one that fills the hole in b...

The intention of fill_bits is to create a number that contains all of
the bits of all of the numbers from min_v to max_v.  In other words:

min_v | (min_v + 1) | (min_v + 2) | ... | (max_v - 1) | max_v

It does this by considering each bit separately.  For each bit 'i', is
there a number 'n' with that bit set such that 'min_v <= n <= max_v'?

'min_v | (1 << i)' is my attempt at calculating the smallest number with
bit 'i' set that satisfies 'min_v | (1 << i)'.  This is incorrect.
Correct would be
'(min_v & (1 << i)) ? min_v : ((min_v >> i) << i) | (1 << i)'.

My other mistake is this bit:
  max_c = min(
     max_a | fill_bits(min_b, max_b),
     max_b | fill_bits(min_a, max_a));
This is my attempt to get a tighter fit than
'fill_bits(min_a, max_a) | fill_bits(min_b, max_b)'.  It doesn't work
correctly, as you have pointed out.

Here is my revised attempt, with those errors corrected:

uint fill_bits(uint min_v, uint max_v) {
  uint mask = min_v;
  for (int i = 0; i < 32; ++i) {
    if ((min_v & (1 << i)) == 0) {
      if ((((min_v >> i) << i) | (1 << i)) <= max_v) {
        mask |= (1 << i);
      }
    }
  }
  return mask;
}

max_c = fill_bits(min_a, max_a) | fill_bits(min_b, max_b);


-- 
Rainer Deyke - rainerd at eldwood.com