homepage

> 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).