robert king - 1 month ago 12
Python Question

# Compute fast log base 2 ceiling in python

for given

`x < 10^15`
, quickly and accurately determine the maximum integer
`p`
such that
`2^p <= x`

Here are some things I've tried:

First I tried this but it's not accurate for large numbers:

``````>>> from math import log
>>> x = 2**3
>>> x
8
>>> p = int(log(x, 2))
>>> 2**p == x
True
>>> x = 2**50
>>> p = int(log(x, 2))
>>> 2**p == x #not accurate for large numbers?
False
``````

I could try something like:

``````p = 1
i = 1
while True:
if i * 2 > n:
break
i *= 2
p += 1
not_p = n - p
``````

Which would take up to 50 operations if p was 50

I could pre-compute all the powers of 2 up until 2^50, and use binary search to find p. This would take around log(50) operations but seems a bit excessive and ugly?

I found this thread for C based solutions: Compute fast log base 2 ceiling

However It seems a bit ugly and I wasn't exactly sure how to convert it to python.

In Python >= 2.7, you can use the `.bit_length()` method of integers:

``````def brute(x):
# determine max p such that 2^p <= x
p = 0
while 2**p <= x:
p += 1
return p-1

def easy(x):
return x.bit_length() - 1
``````

which gives

``````>>> brute(0), brute(2**3-1), brute(2**3)
(-1, 2, 3)
>>> easy(0), easy(2**3-1), easy(2**3)
(-1, 2, 3)
>>> brute(2**50-1), brute(2**50), brute(2**50+1)
(49, 50, 50)
>>> easy(2**50-1), easy(2**50), easy(2**50+1)
(49, 50, 50)
>>>
>>> all(brute(n) == easy(n) for n in range(10**6))
True
>>> nums = (max(2**x+d, 0) for x in range(200) for d in range(-50, 50))
>>> all(brute(n) == easy(n) for n in nums)
True
``````
Source (Stackoverflow)