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

- Steven Schveighoffer (8/12) Apr 16 2010 I solved already signed values in terms of any valid unsigned solution, ...
- Andrei Alexandrescu (11/28) Apr 16 2010 That looks good. I'm thinking of expressing minOR for unsigned in terms
- =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= (44/87) Apr 17 2010 ars.D&article_id=3D108916
- Don (8/92) Apr 19 2010 I think your code looks a lot simpler if you define:
- =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= (19/116) Apr 19 2010 lmars.D&article_id=3D108916
- Steven Schveighoffer (22/56) Apr 19 2010 No, I think you want to maximize the value of ~a & ~b (you have to swap ...

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: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? AndreiLooks 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).

Apr 16 2010

Andrei Alexandrescu wrote:On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:ars.D&article_id=3D108869Andrei 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=3D108916The 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).=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=sin ~a|~b. So: =20 minOR =3D=3D maxOR(~max_a, ~min_a, ~max_b, ~min_b) =20 Works? =20Assuming 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: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.On 04/16/2010 11:43 PM, Steven Schveighoffer wrote: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). JeromeAndrei Alexandrescu Wrote: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?

Apr 19 2010

Don wrote:J=E9r=F4me M. Berger wrote:lmars.D&article_id=3D108869Andrei Alexandrescu wrote:On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:Andrei Alexandrescu Wrote:lmars.D&article_id=3D108916The 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=msx86 bsr instruction (std.instrinsic.bsr).That looks good. I'm thinking of expressing minOR for unsigned in ter=n_a.of maxOR for one's complement. We have min_a <=3D a <=3D max_a. This implies ~max_a <=3D ~a <=3D ~mi=sWavehanding follows. We're looking for the numbers a and b that minimize the number of bit=itsin a|b. Those choices for a and b would then maximize the number of b==3D=3D=3D=3D=3D=3D8<------------------------------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=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3Duint32_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=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.frThe 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=

Apr 19 2010

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: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. -SteveAndrei Alexandrescu Wrote: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?

Apr 19 2010