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

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=


  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=


  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.
=20
 We have min_a <=3D a <=3D max_a. This implies ~max_a <=3D ~a <=3D ~min_=

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

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

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?

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

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?

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

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?

solution, see here: http://www.digitalmars.com/webnews/newsgroups.php?art_group=3Ddigita=




  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=




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




 of maxOR for one's complement.

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



 Wavehanding follows.

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



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



 in ~a|~b. So:

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

 Works?

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=


 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=


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

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