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:


 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
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
next sibling parent reply =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeberger free.fr> writes:
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
parent reply Don <nospam nospam.com> writes:
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
parent =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeberger free.fr> writes:
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
prev sibling parent "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