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.
