www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: value range propagation for _bitwise_ OR

reply Steven Schveighoffer <schveiguy yahoo.com> writes:
Andrei Alexandrescu Wrote:


 On 04/10/2010 12:01 PM, Andrei Alexandrescu wrote:

 Consider:

 byte c = a | b;

 Say you already know min_a, max_a, min_b, and max_b. How do you compute
 min_c and max_c? I thought of it for a bit and it seems quite tricky.


 Thanks,

 Andrei


 
 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;
 }
 
 The idea is to find the candidate that would fill as many zeros in maxa 
 as possible.
 
 But this is inefficient. I'm wondering whether a simple bitwise 
 manipulation expression could do the trick.


Don't you need to take into account the minimum of b also?  That is, the
candidate needs to be greater than minb.  Because filling in more holes doesn't
necessarily mean biggest number, I don't think it works.

Simple counter case:

a's range is 4 to 5
b's range is 4 to 4

The max value of a | b is 5.

However, I think your function will return 15.

Also, you may to use the max of the smaller number.  For example:

a's range is 3 to 5
b's range is 4 to 4
The max number here is 7, but only when a is 3 and b is 4.  With your method,
you automatically assume the number with the highest max value should be at its
max value.

I think this is going to need a recursive solution, but I haven't yet wrapped
my brain around how it needs to work.  I think you should start by assuming for
a given range, mina to maxa, you know that the top 1-bits from ~(mina ^ maxa)
will always be in the result, same with b.  If you eliminate those bits, the
problem gets narrower.  I feel like a good solution first eliminates those,
then decides how to set the next bit, and recurses.  I'm sure there's some sort
of method to decide how to set the bit in order to avoid brute force, but I
haven't thought about it enough.

-Steve
Apr 10 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/10/2010 09:51 PM, Steven Schveighoffer wrote:

 Andrei Alexandrescu Wrote:


 On 04/10/2010 12:01 PM, Andrei Alexandrescu wrote:

 Consider:

 byte c = a | b;

 Say you already know min_a, max_a, min_b, and max_b. How do you
 compute min_c and max_c? I thought of it for a bit and it seems
 quite tricky.


 Thanks,

 Andrei


 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; }

 The idea is to find the candidate that would fill as many zeros in
 maxa as possible.

 But this is inefficient. I'm wondering whether a simple bitwise
 manipulation expression could do the trick.


 Don't you need to take into account the minimum of b also?  That is,
 the candidate needs to be greater than minb.  Because filling in more
 holes doesn't necessarily mean biggest number, I don't think it
 works.


Ha! Good point. I'd forgotten the initial requirement and considered 
both values to start at 0. They don't! Adam? :o)

Andrei
Apr 10 2010
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 10 Apr 2010 22:53:42 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 04/10/2010 09:51 PM, Steven Schveighoffer wrote:

 Andrei Alexandrescu Wrote:


 On 04/10/2010 12:01 PM, Andrei Alexandrescu wrote:

 Consider:

 byte c = a | b;

 Say you already know min_a, max_a, min_b, and max_b. How do you
 compute min_c and max_c? I thought of it for a bit and it seems
 quite tricky.


 Thanks,

 Andrei


 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; }

 The idea is to find the candidate that would fill as many zeros in
 maxa as possible.

 But this is inefficient. I'm wondering whether a simple bitwise
 manipulation expression could do the trick.


 Don't you need to take into account the minimum of b also?  That is,
 the candidate needs to be greater than minb.  Because filling in more
 holes doesn't necessarily mean biggest number, I don't think it
 works.


 Ha! Good point. I'd forgotten the initial requirement and considered  
 both values to start at 0. They don't! Adam? :o)


Couldn't help it, this seems like such a fun problem, I had to solve it :)

uint maxor(uint mina, uint maxa, uint minb, uint maxb)
{
     uint bt = 1 << 31;
     uint result = 0;
     while(bt)
     {
         if((bt & maxa) && (bt & mina))
         {
             result |= bt;
             if((bt & minb) ^ (bt & maxb))
             {
                 return result | (bt-1);// always can choose all 1s for  
rest of b
             }
         }
         else if((bt & maxb) && (bt & minb))
         {
             result |= bt;
             if((bt & mina) ^ (bt & maxa))
             {
                 return result | (bt-1);// always can choose all 1s for  
rest of a
             }
         }
         else if(bt & (maxa | maxb))
         {
             result |= bt;
             if(bt & (maxa & maxb))
             {
                 // both maxa and maxb have bt set, and both mina and minb  
have
                 // bt unset.  This means we can choose this bit to be set  
on
                 // either, and it is possible to have all 1s set for the  
other
                 // for the rest of the bits.
                 return result | (bt - 1);
             }
             else if(bt & maxa)
             {
                 // now that we are using this bit from maxa, we need to  
raise
                 // mina so it becomes the smallest value with bt set.   
However,
                 // we don't really care about bits above bt, so setting
                 // it to 0 is fine.
                 mina = 0;
             }
             else
             {
                 minb = 0;
             }
         }
         // else, neither maxa or maxb have bt set, continue to next bit.
         bt >>= 1;
     }
     return result;
}

This only solves unsigned (tested all ranges against a brute force  
solution up to max values of 64, given the nature of binary, I don't think  
there can be any weird cases that wouldn't have problems at lower ranges.   
Note that in my solution, maxa and maxb are inclusive.

Signed is probably trickier, suppose one is always negative and one is  
always positive!  I'm satisfied solving the unsigned for now, maybe  
someone else can modify this solution to work with signed integers also :)

-Steve
Apr 10 2010
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 11 Apr 2010 00:30:07 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 Couldn't help it, this seems like such a fun problem, I had to solve it  
 :)

 uint maxor(uint mina, uint maxa, uint minb, uint maxb)
 {
      uint bt = 1 << 31;
      uint result = 0;
      while(bt)
      {
          if((bt & maxa) && (bt & mina))
          {
              result |= bt;
              if((bt & minb) ^ (bt & maxb))
              {
                  return result | (bt-1);// always can choose all 1s for  
 rest of b
              }
          }
          else if((bt & maxb) && (bt & minb))
          {
              result |= bt;
              if((bt & mina) ^ (bt & maxa))
              {
                  return result | (bt-1);// always can choose all 1s for  
 rest of a
              }
          }
          else if(bt & (maxa | maxb))
          {
              result |= bt;
              if(bt & (maxa & maxb))
              {
                  // both maxa and maxb have bt set, and both mina and  
 minb have
                  // bt unset.  This means we can choose this bit to be  
 set on
                  // either, and it is possible to have all 1s set for  
 the other
                  // for the rest of the bits.
                  return result | (bt - 1);
              }
              else if(bt & maxa)
              {
                  // now that we are using this bit from maxa, we need to  
 raise
                  // mina so it becomes the smallest value with bt set.   
 However,
                  // we don't really care about bits above bt, so setting
                  // it to 0 is fine.
                  mina = 0;
              }
              else
              {
                  minb = 0;
              }
          }
          // else, neither maxa or maxb have bt set, continue to next bit.
          bt >>= 1;
      }
      return result;
 }


And the complementary minor:


uint minor(uint mina, uint maxa, uint minb, uint maxb)
{
     uint bt = 1 << 31;
     uint result = 0;
     while(bt)
     {
         if((bt & maxa) && (bt & mina))
         {
             result |= bt;
             if((bt & minb) ^ (bt & maxb))
             {
                 // bt will already be set for a, so set it also for b, this
                 // allows us to have all 0s for the rest of b.  Then we use
                 // mina to get the minimum for the rest of a
                 return result | ((bt-1) & mina);
             }
         }
         else if((bt & maxb) && (bt & minb))
         {
             result |= bt;
             if((bt & mina) ^ (bt & maxa))
             {
                 // ditto for b
                 return result | ((bt-1) & minb);
             }
         }
         else
         {
             if(bt & maxa)
             {
                 // we never want to choose a 1 here, so we want a zero,  
which
                 // makes the max for the rest of the bits all 1s.
                 maxa = ~0;
             }

             if(bt & maxb)
             {
                 // ditto for b
                 maxb = ~0;
             }
         }
         bt >>=1;
     }
     return result;
}

I tried to combine these into one function, but the cases are subtly  
different, so you end up just doing each in sequence.  The only thing you  
save is an extra function call and you can combine both loops into one.

I'll work on signed values tomorrow :)

-Steve
Apr 11 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/11/2010 10:07 PM, Steven Schveighoffer wrote:
[snip]

 I'll work on signed values tomorrow :)


This is great work, Steve!

Andrei
Apr 12 2010
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 11 Apr 2010 00:30:07 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 Signed is probably trickier, suppose one is always negative and one is  
 always positive!


Turns out signed is really easy once you have unsigned solved.

Here is minor and maxor for signed assuming unsigned is solved:

int maxor(int mina, int maxa, int minb, int maxb)
{
     if(mina < 0 && maxa >= 0)
     {
         int result = maxor(0, maxa, minb, maxb);
         return result > -1 ? result : -1;
     }
     if(minb < 0 && maxb >= 0)
     {
         int result = maxor(mina, maxa, 0, maxb);
         return result > -1 ? result : -1;
     }
     return cast(int)maxor(cast(uint)mina, cast(uint)maxa, cast(uint)minb,  
cast(uint)maxb);
}

int minor(int mina, int maxa, int minb, int maxb)
{
     if(mina < 0 && maxa >= 0)
     {
         int result = minor(mina, -1, minb, maxb);
         return result < minb ? result : minb;
     }
     if(minb < 0 && maxb >= 0)
     {
         int result = minor(mina, maxa, minb, -1);
         return result < mina ? result : mina;
     }
     return cast(int)minor(cast(uint)mina, cast(uint)maxa, cast(uint)minb,  
cast(uint)maxb);
}

The trick is to avoid dealing with a range that crosses the 0 boundary.   
The negative range isn't any different than an unsigned range -- set the  
most possible bits for max, unset the most possible bits for min.  The  
sign bit simply becomes a hard-wired bit.

BTW, I release this code into the public domain, use it for any purpose  
you wish.

-Steve
Apr 12 2010
prev sibling next sibling parent reply "Adam D. Ruppe" <destructionator gmail.com> writes:
On Sat, Apr 10, 2010 at 09:53:42PM -0500, Andrei Alexandrescu wrote:

 Ha! Good point. I'd forgotten the initial requirement and considered 
 both values to start at 0. They don't! Adam? :o)


Yeah, my big brute-force tester program ran loops for min_a and min_b too.
And it tripped an assert.

core.exception.AssertError or.d(60): [10, 10]. expected: 3, got 2 (min == 2)

I hacked it by only asserting if the mins are zero too... but I did mention
it a couple of times in my spam as the day has gone on.

I'm going to lecture a bit in this post. It is mostly for my benefit - maybe
if I write up the patterns and thoughts explicitly, something new will come
to mind.


My current solution uses a pattern I noticed:

0100
1000

There, the best you get is 1100.

But,

0100
1100

Lets you get to 1111. The reason is that duplicated one in there means you
can trade a 100 for a 011, and still OR in the 100 thanks to the duplicate.

So, I take the two numbers and OR them together, but then, if there is
a bit duplicated, I trade one of them for all the following ones, and
or that in too.

That leads to the one liner solution: return a | ((1 << numbits(a&b)) - 1) | b;

We OR the two values, then use AND to find duplicated bits. We take the
biggest one and trade it out (a power of two minus one gives us all those
ones).

If there are no duplicated bits, a&b == 0, and 1 << 1 == 1, and 1 - 1 = 0,
so it means no change, the correct solution!



Now, here's the problem: what if all those ones are unavailable due to the
minimum value? The example I've been using is (4, 4). It would be nice to
trade one of those 4's for a 3, but if the min value for each is also 4,
this is impossible. The formula above would give 7, but this limitation
means you can't get bigger than 4.

A minimum of one is fine still - it is the same as zero due to how OR works.
The problem is a minimum of two or more. This cuts off ones from the right.

Oh, but not necessarily! You get a one on the end for ALL odd numbers, so
unless the min == max && !(max&1), you get the one on the end.

So, the bigger the gap, the smaller our mask. Since the interval is inclusive,
the most significant set bits on each max can never be masked out.


We'll use that as the starting point and write up a loop solution. We start
at the right - the ones place - and or it in if the bit is available.

It looks like the another AND filter applied to the AND that's there, but
instead of using numbits(a&b), we should use numbits(something_min).

Which one are we carrying those ones from? Either, really. So as long as
either one works, we should be ok.

Let's try it.

Nope :( The max is now too small.

Gah, I need to get to bed. Here's what I have:

=========
uint max_c(uint max_a, uint max_b, uint min_a, uint min_b) {
	uint tmp = max_a | max_b;

	uint true_min = min(min_a, min_b);
	if(min_a <= 1 || min_b <= 1)
		tmp |= ((1 << numbits(max_a&max_b)) - 1);
	else {
		// THIS PORTION IS WRONG
		tmp |= ((1 << numbits(max_a&max_b)) - 1);
		uint mask = min(msb(max_a), msb(max_b)) - 1;

		for(uint v = 1; v < mask; v <<= 1) {
			if(true_min - v && !(true_min & v))
				mask &= ~v;
		}

		tmp &= ~mask;
	}
	return tmp;
}
=========


-- 
Adam D. Ruppe
http://arsdnet.net
Apr 10 2010
parent Nathan Tuggy <bugzilla nathan.tuggycomputer.com> writes:
I normally lurk here, because I don't have any projects that use D and 
thus I haven't really learned it. But I just wanted to say that this 
problem, and the three threads of solutions, constitute one of the most 
fascinating discussions I've seen on the newsgroups in quite a while -- 
probably because I can almost solve the basic problem myself (though 
doubtless very sub-optimally).

Anyway, the strangeness of this particular problem is really very 
entrancing. I could sit and think about it all day -- except that it 
makes my brain hurt ;-).

On 2010-04-10 21:45, Adam D. Ruppe wrote:

 On Sat, Apr 10, 2010 at 09:53:42PM -0500, Andrei Alexandrescu wrote:

 Ha! Good point. I'd forgotten the initial requirement and considered
 both values to start at 0. They don't! Adam? :o)


 Yeah, my big brute-force tester program ran loops for min_a and min_b too.
 And it tripped an assert.

 core.exception.AssertError or.d(60): [10, 10]. expected: 3, got 2 (min == 2)

 I hacked it by only asserting if the mins are zero too... but I did mention
 it a couple of times in my spam as the day has gone on.

 I'm going to lecture a bit in this post. It is mostly for my benefit - maybe
 if I write up the patterns and thoughts explicitly, something new will come
 to mind.


 My current solution uses a pattern I noticed:

 0100
 1000

 There, the best you get is 1100.

 But,

 0100
 1100

 Lets you get to 1111. The reason is that duplicated one in there means you
 can trade a 100 for a 011, and still OR in the 100 thanks to the duplicate.

 So, I take the two numbers and OR them together, but then, if there is
 a bit duplicated, I trade one of them for all the following ones, and
 or that in too.

 That leads to the one liner solution: return a | ((1<<  numbits(a&b)) - 1) | b;

 We OR the two values, then use AND to find duplicated bits. We take the
 biggest one and trade it out (a power of two minus one gives us all those
 ones).

 If there are no duplicated bits, a&b == 0, and 1<<  1 == 1, and 1 - 1 = 0,
 so it means no change, the correct solution!



 Now, here's the problem: what if all those ones are unavailable due to the
 minimum value? The example I've been using is (4, 4). It would be nice to
 trade one of those 4's for a 3, but if the min value for each is also 4,
 this is impossible. The formula above would give 7, but this limitation
 means you can't get bigger than 4.

 A minimum of one is fine still - it is the same as zero due to how OR works.
 The problem is a minimum of two or more. This cuts off ones from the right.

 Oh, but not necessarily! You get a one on the end for ALL odd numbers, so
 unless the min == max&&  !(max&1), you get the one on the end.

 So, the bigger the gap, the smaller our mask. Since the interval is inclusive,
 the most significant set bits on each max can never be masked out.


 We'll use that as the starting point and write up a loop solution. We start
 at the right - the ones place - and or it in if the bit is available.

 It looks like the another AND filter applied to the AND that's there, but
 instead of using numbits(a&b), we should use numbits(something_min).

 Which one are we carrying those ones from? Either, really. So as long as
 either one works, we should be ok.

 Let's try it.

 Nope :( The max is now too small.

 Gah, I need to get to bed. Here's what I have:

 =========
 uint max_c(uint max_a, uint max_b, uint min_a, uint min_b) {
 	uint tmp = max_a | max_b;

 	uint true_min = min(min_a, min_b);
 	if(min_a<= 1 || min_b<= 1)
 		tmp |= ((1<<  numbits(max_a&max_b)) - 1);
 	else {
 		// THIS PORTION IS WRONG
 		tmp |= ((1<<  numbits(max_a&max_b)) - 1);
 		uint mask = min(msb(max_a), msb(max_b)) - 1;

 		for(uint v = 1; v<  mask; v<<= 1) {
 			if(true_min - v&&  !(true_min&  v))
 				mask&= ~v;
 		}

 		tmp&= ~mask;
 	}
 	return tmp;
 }
 =========
Apr 10 2010
prev sibling parent reply Rainer Deyke <rainerd eldwood.com> writes:
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));


-- 
Rainer Deyke - rainerd eldwood.com
Apr 10 2010
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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...

This problem has nothing directly to do with values, it has something to 
do with parts of values. The parts of values cannot be decided by 
looking at only a pair.

Here are some values that the algorithm fails with ("mask" is printed 
before returning from fill_bits) :

                  binary     decimal
-----------------------------------
             mask 0000000011     3
             mask 0111111111   511
            min_a 0000100100    36
            max_a 0101100011   355
            min_b 0000000001     1
            max_b 0000000100     4
       calculated 0101100011   355
WRONG! empirical 0101100111   359
        emp_max_a 0101100011   355
        emp_max_b 0000000100     4

The last two lines are telling: An unsuspected value of b happens to be 
the one that produces the maximum value of a|b.

Ali
Apr 11 2010
parent reply Rainer Deyke <rainerd eldwood.com> writes:
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 eldwood.com
Apr 11 2010
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
Rainer Deyke wrote:


 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.


But no value in the range may have all those bits set. As a result, a|b 
may have less bits set than fill_bits returns.


 In other words:

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


That's the problem: Only one of those values is used in a|b at a time.

Here is the test code that I've been using when I tried to solve this 
problem:

import std.random;
import std.stdio;

void report(string label, uint value)
{
     writefln("%25s %032b %08x %10s", label, value, value, value);
}

// ...

unittest
{
     foreach (i; 0 .. 1000) {

         uint max_a = uniform(0, 1024);
         uint min_a = uniform(0, max_a + 1);

         uint max_b = uniform(0, 1024);
         uint min_b = uniform(0, max_b + 1);

         uint calculated_max_c = max_c_Deyke_2(min_a, max_a, min_b, max_b);

         report("min_a", min_a);
         report("max_a", max_a);
         report("min_b", min_b);
         report("max_b", max_b);
         report("calculated", calculated_max_c);

         uint emp_max_a;
         uint emp_max_b;
         uint empirical_max_c;
         foreach (a; min_a .. max_a + 1) {
             foreach(b; min_b .. max_b + 1) {
                 if ((a | b) > empirical_max_c) {
                     emp_max_a = a;
                     emp_max_b = b;
                     empirical_max_c = a | b;
                 }
             }
         }

         if (empirical_max_c != calculated_max_c) {
             report("WRONG! empirical", empirical_max_c);
             report("emp_max_a", emp_max_a);
             report("emp_max_b", emp_max_b);
             break;
         }
     }
}

Yes, it's incomplete, but does catch problems. :) So far, Steven 
Schveighoffer's maxor() is the only one that passes the tests. (There 
may be other solutions that I've missed.)

Ali
Apr 11 2010
next sibling parent =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Ali =C3=87ehreli wrote:

 Yes, it's incomplete, but does catch problems. :) So far, Steven
 Schveighoffer's maxor() is the only one that passes the tests. (There
 may be other solutions that I've missed.)
=20


	I suggest you triple-check your implementations of everyone's
algorithms since the counter-example you found for my algorithm is
wrong (i.e my code gives the correct result).

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
Apr 11 2010
prev sibling parent reply Rainer Deyke <rainerd eldwood.com> writes:
On 4/11/2010 13:16, Ali Çehreli wrote:

 Rainer Deyke wrote:
 

 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.


 
 But no value in the range may have all those bits set. As a result, a|b
 may have less bits set than fill_bits returns.


Yes, my (revised) function is (still) conservative.  It may result in a
larger range than strictly necessary, but it should never result in a
smaller range.

If you want 100% percent accuracy then you probably shouldn't be using
(min, max) pairs to represent your ranges anyway, since this is already
a simplification.  For example:

uint a = x & 0x8000_0000;

Here, the compiler can know a lot about 'a'.  'a' must have one of
exactly two values: 0 and 0x8000_0000.  However, if the compiler
represents this information the form of a (min, max) pair, then all it
knows is that 'a' is somewhere in the range from 0 to 0x8000_0000.  This
is especially an issue when bitwise operations are chained.  Consider:

uint b = a & 0x7fff_ffff;

Now you and I know that 'b' must be exactly 0, given the above
assignment to 'a'.  However, using (min, max) range tracking, all that
the compiler knows is that 'b' is somewhere in the range from 0 to
0x7fff_ffff.


-- 
Rainer Deyke - rainerd eldwood.com
Apr 11 2010
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke <rainerd eldwood.com>  
wrote:


 On 4/11/2010 13:16, Ali Çehreli wrote:

 Rainer Deyke wrote:


 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.


 But no value in the range may have all those bits set. As a result, a|b
 may have less bits set than fill_bits returns.


 Yes, my (revised) function is (still) conservative.  It may result in a
 larger range than strictly necessary, but it should never result in a
 smaller range.


It is possible to get an exact range in O(lgn) time.


 If you want 100% percent accuracy then you probably shouldn't be using
 (min, max) pairs to represent your ranges anyway, since this is already
 a simplification.


Range propagation is needed to determine if you can put a value into a  
smaller type.  At that point, all that is needed is the min and max.   
However, you are correct that without more data, the compiler might reject  
legitimate implicit casts that are easily proven.

Would (min, max, mask) be enough to allow this?  Or do we need an exact  
list...

-Steve
Apr 11 2010
next sibling parent reply Rainer Deyke <rainerd eldwood.com> writes:
On 4/11/2010 20:51, Steven Schveighoffer wrote:

 Range propagation is needed to determine if you can put a value into a
 smaller type.  At that point, all that is needed is the min and max. 


Technically, you don't even need min and max at that point.  A bit mask
would be enough.


 However, you are correct that without more data, the compiler might
 reject legitimate implicit casts that are easily proven.
 
 Would (min, max, mask) be enough to allow this?  Or do we need an exact
 list...


I was think about two masks (min_mask and max_mask) such that
'(min_mask & x) == min_mask' and '(max_mask | x) == max_mask'.  In other
words, 'min_mask' contains the bits that are definitely 1 in 'x' while
'max_mask' contains the bits that /could/ be 1 in 'x'.  This avoids loss
of information in the presence of the bitwise inverse operator (unary '~').


-- 
Rainer Deyke - rainerd eldwood.com
Apr 11 2010
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 12 Apr 2010 01:11:37 -0400, Rainer Deyke <rainerd eldwood.com>  
wrote:


 On 4/11/2010 20:51, Steven Schveighoffer wrote:

 Range propagation is needed to determine if you can put a value into a
 smaller type.  At that point, all that is needed is the min and max.


 Technically, you don't even need min and max at that point.  A bit mask
 would be enough.


Only for unsigned types...

-Steve
Apr 12 2010
prev sibling parent reply =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Steven Schveighoffer wrote:

 On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke <rainerd eldwood.com>
 wrote:
=20

 On 4/11/2010 13:16, Ali =C3=87ehreli wrote:

 Rainer Deyke wrote:


 The intention of fill_bits is to create a number that contains all o=








f

 the bits of all of the numbers from min_v to max_v.


 But no value in the range may have all those bits set. As a result, a=






|b

 may have less bits set than fill_bits returns.


 Yes, my (revised) function is (still) conservative.  It may result in =




a

 larger range than strictly necessary, but it should never result in a
 smaller range.


=20
 It is possible to get an exact range in O(lgn) time.
=20

 If you want 100% percent accuracy then you probably shouldn't be using=





 (min, max) pairs to represent your ranges anyway, since this is alread=




y

 a simplification.


=20
 Range propagation is needed to determine if you can put a value into a
 smaller type.


	If that was all we wanted, we wouldn't need to have a precise maxOr
since the output of the "or" operation is guaranteed to fit in the
same width as the operands. The reason we need to be precise is for
future propagation, at which point being able to handle holes in the
range could be useful (but too expensive in both time and memory to
be practical in a compiler).

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
Apr 12 2010
parent reply Don <nospam nospam.com> writes:
Jérôme M. Berger wrote:

 Steven Schveighoffer wrote:

 On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke <rainerd eldwood.com>
 wrote:


 On 4/11/2010 13:16, Ali Çehreli wrote:

 Rainer Deyke wrote:


 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.


 But no value in the range may have all those bits set. As a result, a|b
 may have less bits set than fill_bits returns.


 Yes, my (revised) function is (still) conservative.  It may result in a
 larger range than strictly necessary, but it should never result in a
 smaller range.


 It is possible to get an exact range in O(lgn) time.


 If you want 100% percent accuracy then you probably shouldn't be using
 (min, max) pairs to represent your ranges anyway, since this is already
 a simplification.


 Range propagation is needed to determine if you can put a value into a
 smaller type.


 
 	If that was all we wanted, we wouldn't need to have a precise maxOr
 since the output of the "or" operation is guaranteed to fit in the
 same width as the operands. The reason we need to be precise is for
 future propagation, at which point being able to handle holes in the
 range could be useful (but too expensive in both time and memory to
 be practical in a compiler).
 
 		Jerome


Remember that the OR may be part of a larger expression. There may be 
something like:

uint a, b;
ubyte c = (a|b) + 6;
Apr 12 2010
parent =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Don wrote:

 J=C3=A9r=C3=B4me M. Berger wrote:

 Steven Schveighoffer wrote:

 On Sun, 11 Apr 2010 22:36:33 -0400, Rainer Deyke <rainerd eldwood.com=





 wrote:

 On 4/11/2010 13:16, Ali =C3=87ehreli wrote:

 Rainer Deyke wrote:


 If you want 100% percent accuracy then you probably shouldn't be usi=








ng

 (min, max) pairs to represent your ranges anyway, since this is alre=








ady

 a simplification.


 Range propagation is needed to determine if you can put a value into =






a

 smaller type.


     If that was all we wanted, we wouldn't need to have a precise maxO=




r

 since the output of the "or" operation is guaranteed to fit in the
 same width as the operands. The reason we need to be precise is for
 future propagation, at which point being able to handle holes in the
 range could be useful (but too expensive in both time and memory to
 be practical in a compiler).

         Jerome


=20
 Remember that the OR may be part of a larger expression. There may be
 something like:
=20
 uint a, b;
 ubyte c =3D (a|b) + 6;
=20


	That is why I started my reply with "if that was all we wanted"...

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
Apr 12 2010