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