Jerome's highbit function is the same as std.intrinsic.bsr. I wonder
which is faster?
I ran a test, and for 100 million iterations (1..10000000), the
intrinsic beat out his function be a mere 300 milliseconds on my box.
- highbit ran in an average of 1897 ms and bsr did the same in an
average if 1534.
Recompiling with -inline -O -release cuts the raw numbers about in
half, but keeps about the same difference, leading me to think
overhead amounts for a fair amount of the percentage instead of actual
implementation. The new averages are 1134 and 853.
I've gotta say, your implementation of the function is better than I
would have done though. Without bsr, I probably would have looped,
shifted, and tested each individual bit...
On 4/13/10, Steven Schveighoffer <schvei...@yahoo.com> 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
>
