Mark Dickinson <dicki...@gmail.com> added the comment:
> Did you look at the O(lg n) algorithm yet? Any thoughts?
So there are two places this could be applied: the int_numbits method
and _PyLong_NumBits. I'd be quite surprised if this offered any
noticeable speedup in either case. Might be worth a try, though---I'll
see if I can get some timings.
For int_numbits, it would have to be implemented in a way that works for
32-bit and 64-bit C longs. And if it also just happens to work for
other sizes, that would be good, too. I'd probably try something like:
while (v > 0xFFFFFFFF) {
bitcount += 32;
v >>= 32;
}
before doing a 32-bit bitcount on what's left. On a 32-bit machine,
the whole while loop should just be optimized away to nothing.
Similarly, in _PyLong_NumBits it would be good if it could be
implemented in a way that doesn't have to change if/when PyLong_SHIFT is
changed.
I prefer the second variant given (the non-branching version).
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue3439>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
