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
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 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 next 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:
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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

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
next sibling parent 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
prev sibling parent reply =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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=




 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=



 may have less bits set than fill_bits returns.

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


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


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

may have less bits set than fill_bits returns.

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.

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:
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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:





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




 a simplification.




 smaller type.

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


 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: =20 uint a, b; ubyte c =3D (a|b) + 6; =20

Jerome --=20 mailto:jeberger free.fr http://jeberger.free.fr Jabber: jeberger jabber.fr
Apr 12 2010
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next 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 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