how to get the thighest bit position in big integers?

[Duncan Booth]

"Aaron \"Castironpi\" Brady" <castironpi at gmail.com> wrote:

>> OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433222211111111"))
>> def get_highest_bit_num(r):
>>      s = "%x"%r
>>      return len(s) * 4 - OFFSET[s[0]]
> 
> You can replace the dict if it's faster.
> 
> OFFSET= tuple( int(x) for x in "5433222211111111" )
> def get_highest_bit_num(r):
>      s = "%x"%r
>      return len(s) * 4 - OFFSET[int(s[0],16)]
> 
> P.S.  Back home, this sort of 'nitpicking' would be judged 
> unconstructive.  Worth pointing out, or not worth saying?
> 
You could have answered your own question fairly quickly using the 'timeit' 
module. In this case you trade off the dict lookup for a global name lookup 
and a function call so I'd expect you would have made it slower and indeed 
it seems to be about 30-40% slower than mine.

The math.floor/math.log version isn't so good for small values, but both 
string versions seem to slow down dramatically somewhere around 526 bits 
(2.8uS suddenly jumps to about 4us while the math version stays roughly 
steady around 3.2uS).