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

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
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
"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
"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
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
"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
"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))
}

}
return tmp;
}
=========

--
http://arsdnet.net
```
Apr 10 2010
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))
}

}
return tmp;
}
=========

```
Apr 10 2010
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);
}
}

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
=?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
```Rainer Deyke wrote:

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

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
-----------------------------------
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
Rainer Deyke <rainerd eldwood.com> writes:
```On 4/11/2010 11:16, Ali Çehreli wrote:
Rainer Deyke wrote:

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

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

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

--
Rainer Deyke - rainerd eldwood.com
```
Apr 11 2010
=?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
=?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
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
"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
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...

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
"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
=?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
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
=?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=

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