Steven Schveighoffer wrote:
On Mon, 12 Apr 2010 22:37:00 -0400, Steven Schveighoffer
<schvei...@yahoo.com> wrote:
Jérôme M. Berger Wrote:
Steven Schveighoffer wrote:
> Fails for test case:
>
> minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result
is 6).
>
Nope, outputs 6. Note that I've run an exhaustive search for all
combinations in the [0, 63] range, so if there are mistakes they
have to be outside that range...
I'll have to double check, I thought I copied your code verbatim (I
did switch around the arguments to be minA, maxA, minB, maxB to fit my
test harness, and I changed the uint_32_t to uint). I'll check
tomorrow at work where the computer I used to test is.
I confirm, with the updated highbit, your solution works.
Also, inspired by your solution (and using your highbit function, which
is very neat BTW) I came up with a one-liner. Enjoy :)
uint maxor(uint mina, uint maxa, uint minb, uint maxb)
{
return maxa | maxb | ((1 << highbit(((1 << (max(highbit(mina ^
maxa), highbit(minb ^ maxb)) + 1)) - 1) & maxa & maxb)) - 1);
}
Anyone want to do the equivalent minor? I've spent way too much time on
this :)
-Steve
Awesome stuff, guys.
I think that's worthy of inclusion as an exercise in Knuth's Volume 4,
fascile 1. Suggest it to someone at ACCU?
(Knuth has highbit(x) but calls it lambda(x). He notes the result that
highbit(x)==highbit(y) iff x^y <= x&y).
