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
