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

```Andrei Alexandrescu Wrote:

Looks great, thanks Jerome!

Now, how about that case in which some or all of the ranges involved
include negative values?

I solved already signed values in terms of any valid unsigned solution, see
here: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108869

The maxor with all the unsigned casts is the call to the unsigned maxor.  Ditto
for minor.

Also, see my one liner for unsigned maxor:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108916

All that is left is to find a quick (possibly one liner?) minor for unsigned.
Maybe there's a quicker signed solution, but the complexity is already O(1) *
complexity of unsigned.

Also, someone pointed out that Jerome's highbit is equivalent to the x86 bsr
instruction (std.instrinsic.bsr).

-Steve
```
Apr 16 2010
```On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:

Looks great, thanks Jerome!

Now, how about that case in which some or all of the ranges
involved include negative values?

I solved already signed values in terms of any valid unsigned
solution, see here:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108869

The maxor with all the unsigned casts is the call to the unsigned
maxor.  Ditto for minor.

Also, see my one liner for unsigned maxor:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108916

All that is left is to find a quick (possibly one liner?) minor for
unsigned.  Maybe there's a quicker signed solution, but the
complexity is already O(1) * complexity of unsigned.

Also, someone pointed out that Jerome's highbit is equivalent to the
x86 bsr instruction (std.instrinsic.bsr).

That looks good. I'm thinking of expressing minOR for unsigned in terms
of maxOR for one's complement.

We have min_a <= a <= max_a. This implies ~max_a <= ~a <= ~min_a.

Wavehanding follows.

We're looking for the numbers a and b that minimize the number of bits
in a|b. Those choices for a and b would then maximize the number of bits
in ~a|~b. So:

minOR == maxOR(~max_a, ~min_a, ~max_b, ~min_b)

Works?

Andrei
```
Apr 16 2010
```Andrei Alexandrescu wrote:
On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:

Looks great, thanks Jerome!

Now, how about that case in which some or all of the ranges
involved include negative values?

I solved already signed values in terms of any valid unsigned
solution, see here:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=3Ddigitalm=

ars.D&article_id=3D108869
The maxor with all the unsigned casts is the call to the unsigned
maxor.  Ditto for minor.

Also, see my one liner for unsigned maxor:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=3Ddigitalm=

ars.D&article_id=3D108916
All that is left is to find a quick (possibly one liner?) minor for
unsigned.  Maybe there's a quicker signed solution, but the
complexity is already O(1) * complexity of unsigned.

Also, someone pointed out that Jerome's highbit is equivalent to the
x86 bsr instruction (std.instrinsic.bsr).

=20
That looks good. I'm thinking of expressing minOR for unsigned in terms=

of maxOR for one's complement.
=20
We have min_a <=3D a <=3D max_a. This implies ~max_a <=3D ~a <=3D ~min_=

a.
=20
Wavehanding follows.
=20
We're looking for the numbers a and b that minimize the number of bits
in a|b. Those choices for a and b would then maximize the number of bit=

s
in ~a|~b. So:
=20
minOR =3D=3D maxOR(~max_a, ~min_a, ~max_b, ~min_b)
=20
Works?
=20

Assuming you meant:

minOR =3D=3D ~maxOR(~max_a, ~min_a, ~max_b, ~min_b)

Then that was my first idea too but it is *very* conservative. In
my tests it only gave the best result for 0.1% of the time. So we'll
have to do it the hard way:

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D8<------------------------------
uint32_t minOr (uint32_t minA, uint32_t minB,
uint32_t maxA, uint32_t maxB)
{
assert (minA <=3D maxA);
assert (minB <=3D maxB);

if (minA =3D=3D 0) return minB;
if (minB =3D=3D 0) return minA;

uint32_t a =3D maxA ^ minA;
if (a !=3D 0) {
a =3D ((1 << (highbit (a)+1)) - 1) & ~minA & minB;
if (a !=3D 0)
a =3D (1 << highbit (a)) - 1;
}
a =3D minA & ~a;

uint32_t b =3D maxB ^ minB;
if (b !=3D 0) {
b =3D ((1 << (highbit (b)+1)) - 1) & ~minB & minA;
if (b !=3D 0)
b =3D (1 << highbit (b)) - 1;
}
b =3D minB & ~b;

return min (minA|b, a|minB);
}
------------------------------>8=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

The one-liner is left as an exercise to the readers (since it has
the same performance anyway).

Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
```
Apr 17 2010
```J�r�me M. Berger wrote:
Andrei Alexandrescu wrote:
On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:

Looks great, thanks Jerome!

Now, how about that case in which some or all of the ranges
involved include negative values?

I solved already signed values in terms of any valid unsigned
solution, see here:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108869

The maxor with all the unsigned casts is the call to the unsigned
maxor.  Ditto for minor.

Also, see my one liner for unsigned maxor:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108916

All that is left is to find a quick (possibly one liner?) minor for
unsigned.  Maybe there's a quicker signed solution, but the
complexity is already O(1) * complexity of unsigned.

Also, someone pointed out that Jerome's highbit is equivalent to the
x86 bsr instruction (std.instrinsic.bsr).

That looks good. I'm thinking of expressing minOR for unsigned in terms
of maxOR for one's complement.

We have min_a <= a <= max_a. This implies ~max_a <= ~a <= ~min_a.

Wavehanding follows.

We're looking for the numbers a and b that minimize the number of bits
in a|b. Those choices for a and b would then maximize the number of bits
in ~a|~b. So:

minOR == maxOR(~max_a, ~min_a, ~max_b, ~min_b)

Works?

Assuming you meant:

minOR == ~maxOR(~max_a, ~min_a, ~max_b, ~min_b)

Then that was my first idea too but it is *very* conservative. In
my tests it only gave the best result for 0.1% of the time. So we'll
have to do it the hard way:

==============================8<------------------------------
uint32_t minOr (uint32_t minA, uint32_t minB,
uint32_t maxA, uint32_t maxB)
{
assert (minA <= maxA);
assert (minB <= maxB);

if (minA == 0) return minB;
if (minB == 0) return minA;

uint32_t a = maxA ^ minA;
if (a != 0) {
a = ((1 << (highbit (a)+1)) - 1) & ~minA & minB;
if (a != 0)
a = (1 << highbit (a)) - 1;
}
a = minA & ~a;

uint32_t b = maxB ^ minB;
if (b != 0) {
b = ((1 << (highbit (b)+1)) - 1) & ~minB & minA;
if (b != 0)
b = (1 << highbit (b)) - 1;
}
b = minB & ~b;

return min (minA|b, a|minB);
}
------------------------------>8==============================

The one-liner is left as an exercise to the readers (since it has
the same performance anyway).

Jerome

I think your code looks a lot simpler if you define:

/// return the largest power of 2 such that floor2(x) <= x.
uint floor2(uint x)
{
return x==0 ? x : (1 << bsr(x));
}

since what you're doing is stripping away all bits except the highest one.
```
Apr 19 2010
```Don wrote:
J=E9r=F4me M. Berger wrote:
Andrei Alexandrescu wrote:
On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:

Looks great, thanks Jerome!

Now, how about that case in which some or all of the ranges
involved include negative values?

I solved already signed values in terms of any valid unsigned
solution, see here:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=3Ddigita=

lmars.D&article_id=3D108869
The maxor with all the unsigned casts is the call to the unsigned
maxor.  Ditto for minor.

Also, see my one liner for unsigned maxor:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=3Ddigita=

lmars.D&article_id=3D108916
All that is left is to find a quick (possibly one liner?) minor for=

unsigned.  Maybe there's a quicker signed solution, but the
complexity is already O(1) * complexity of unsigned.

Also, someone pointed out that Jerome's highbit is equivalent to the=

x86 bsr instruction (std.instrinsic.bsr).

That looks good. I'm thinking of expressing minOR for unsigned in ter=

ms
of maxOR for one's complement.

We have min_a <=3D a <=3D max_a. This implies ~max_a <=3D ~a <=3D ~mi=

n_a.
Wavehanding follows.

We're looking for the numbers a and b that minimize the number of bit=

s
in a|b. Those choices for a and b would then maximize the number of b=

its
in ~a|~b. So:

minOR =3D=3D maxOR(~max_a, ~min_a, ~max_b, ~min_b)

Works?

Assuming you meant:

minOR =3D=3D ~maxOR(~max_a, ~min_a, ~max_b, ~min_b)

Then that was my first idea too but it is *very* conservative. In
my tests it only gave the best result for 0.1% of the time. So we'll
have to do it the hard way:

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=

=3D=3D=3D=3D=3D=3D8<------------------------------
uint32_t minOr (uint32_t minA, uint32_t minB,
uint32_t maxA, uint32_t maxB)
{
assert (minA <=3D maxA);
assert (minB <=3D maxB);

if (minA =3D=3D 0) return minB;
if (minB =3D=3D 0) return minA;

uint32_t a =3D maxA ^ minA;
if (a !=3D 0) {
a =3D ((1 << (highbit (a)+1)) - 1) & ~minA & minB;
if (a !=3D 0)
a =3D (1 << highbit (a)) - 1;
}
a =3D minA & ~a;

uint32_t b =3D maxB ^ minB;
if (b !=3D 0) {
b =3D ((1 << (highbit (b)+1)) - 1) & ~minB & minA;
if (b !=3D 0)
b =3D (1 << highbit (b)) - 1;
}
b =3D minB & ~b;

return min (minA|b, a|minB);
}
------------------------------>8=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
The one-liner is left as an exercise to the readers (since it has
the same performance anyway).

Jerome

=20
I think your code looks a lot simpler if you define:
=20
/// return the largest power of 2 such that floor2(x) <=3D x.
uint floor2(uint x)
{
return x=3D=3D0 ? x : (1 << bsr(x));
}
=20
since what you're doing is stripping away all bits except the highest o=

ne.

Actually, most times I'm creating a number with all 1s until the
highest bit, which is sometimes set and sometimes not (twice of each
for minOr, always unset for maxOr)... Your floor2 could be used for
maxOr, but only for two out of four cases in minOr.

Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
```
Apr 19 2010    "Steven Schveighoffer" <schveiguy yahoo.com> writes:
```On Sat, 17 Apr 2010 01:55:26 -0400, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
Andrei Alexandrescu Wrote:

Looks great, thanks Jerome!

Now, how about that case in which some or all of the ranges
involved include negative values?

I solved already signed values in terms of any valid unsigned
solution, see here:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108869

The maxor with all the unsigned casts is the call to the unsigned
maxor.  Ditto for minor.

Also, see my one liner for unsigned maxor:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108916

All that is left is to find a quick (possibly one liner?) minor for
unsigned.  Maybe there's a quicker signed solution, but the
complexity is already O(1) * complexity of unsigned.

Also, someone pointed out that Jerome's highbit is equivalent to the
x86 bsr instruction (std.instrinsic.bsr).

That looks good. I'm thinking of expressing minOR for unsigned in terms
of maxOR for one's complement.

We have min_a <= a <= max_a. This implies ~max_a <= ~a <= ~min_a.

Wavehanding follows.

We're looking for the numbers a and b that minimize the number of bits
in a|b. Those choices for a and b would then maximize the number of bits
in ~a|~b. So:

minOR == maxOR(~max_a, ~min_a, ~max_b, ~min_b)

Works?

No, I think you want to maximize the value of ~a & ~b (you have to swap
the operation too!).

But I think there is a shortcut.  In maxor, I basically searched for the
highest bit that is set in both maxes, and unset in one or both mins.
When you find this bit, then the max in which that bit is optional is set
to 0, and the rest of the value can be 1s.

I think a similar strategy can be used in min.  Essentially, you want to
find the highest bit for which one of the values *must* have it set (that
is (min ^ max) & bit == 0 and max & bit != 0), and for which the other
value has it as optional.  In that case, you set the optional bit to a 1,
and the rest can be all 0s.  Then you or in the min of the other value.

In my original solution, the loop searched for that first bit, and once it
was found, it returned immediately with the shortcut.

I think a one-liner is more difficult for minor because you can't just
'or' both mins together assuming it will not hurt as you can in the max
version (The minimum max value is maxa | maxb, but the minimum min value
is not mina | minb).  The strategy for finding the target bit can be done
in one line.

It might be 2 one-liners in which you just take the min of the results.

-Steve
```
Apr 19 2010