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
--
mailto:[email protected]
http://jeberger.free.fr
Jabber: [email protected]
signature.asc
Description: OpenPGP digital signature
