Find algorithm to base 2 of number without math module

What is the most efficient way to find the logarithm to base 2 of a given number without using math module?

math.log and math.log2 are float operations therefore have inherent accuracy problems and may give false results, but they are very fast.

The number is guaranteed to be a power of 2, the function will only be executed if the following function returns True:

def power_of_2(n):
    return (n & (n-1) == 0) and n != 0

I want the result to be 100% accurate and I have already found a way to achieve this:

def log2(n):
    i = 0
    while n > 1:
        n >>= 1
        i += 1
    return i

performance:

In [244]: def log2(n):
     ...:     i = 0
     ...:     while n > 1:
     ...:         n >>= 1
     ...:         i += 1
     ...:     return i

In [245]: log2(33554432)
Out[245]: 25

In [246]: import math

In [247]: math.log2(33554432)
Out[247]: 25.0

In [248]: %timeit log2(33554432)
2.37 µs ± 208 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [249]: %timeit math.log2(33554432)
125 ns ± 1.34 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

I found bit manipulation more suitable than float operations for this task, how can I improve the performance of the function while using the same logic?

Answer

I have tried to run most of the methods from different answers from 1 and 2 where I found that power_of_2 and easy show a good performance.

import math
import timeit

def myLog(x, b):
    if x < b:
        return 0
    return 1 + float(myLog(x / b, b))


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


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


def log2_approx(val):
    from math import floor
    val = floor(val)
    approx = 0
    while val != 0:
        val &= ~ (1 << approx)
        approx += 1
    return approx


def log2(n):
    i = 0
    while n > 1:
        n >>= 1
        i += 1
    return i


def power_of_2(n):
    return (n & (n - 1) == 0) and n != 0

def log2_fast(n):
    return  math.frexp(33554436)[1] - 1
import time
from functools import partial
 
import time

start_time = time.time()
math.log2(33554432)
print("math.log2 is %s microseconds ---" % ((time.time() - start_time) * 1000000))
start_time = time.time()
myLog(33554432.0, 2.0)
print(" myLog is %s microseconds ---" % ((time.time() - start_time) * 1000000))

start_time = time.time()
brute(33554432)
print(" brute is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))
start_time = time.time()

log2_approx(33554432) - 1
print("log2_approx is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))
start_time = time.time()
log2_fast = math.frexp(33554436)[1] - 1
print(" log2_fast is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))

start_time = time.time()
log2(33554432)
print("log2 is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))

start_time = time.time()
power_of_2(33554432)
print("power_of_2 is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))
start_time = time.time()
easy(33554432)
print("easy is --- %s microseconds ---" % ((time.time() - start_time) * 1000000))

Running time

 math.log2 is 3.0994415283203125 microseconds ---
 myLog is 5.4836273193359375 microseconds ---
 brute is --- 6.4373016357421875 microseconds ---
 log2_approx is --- 6.4373016357421875 microseconds ---
 log2_fast is --- 1.6689300537109375 microseconds ---
 log2 is --- 2.1457672119140625 microseconds ---
 power_of_2 is --- 0.7152557373046875 microseconds ---
 easy is --- 0.476837158203125 microseconds ---

Using timeit shows delay

test_items=33554432
base=2
times = timeit.Timer(partial(math.log2, test_items))
print("math.log2 is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(myLog, test_items,base))
print("myLog is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(easy, test_items))
print("easy is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(brute, test_items))
print("brute is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(log2_approx, test_items))
print("log2_approx is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(log2, test_items))
print("log2 is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(power_of_2, test_items))
print("power_of_2 is %s microseconds ---", (times.timeit(1000000)))
times = timeit.Timer(partial(log2_fast, test_items))
print("log2_fast is %s microseconds ---", (times.timeit(1000000)))

Running time

math.log2 is %s microseconds --- 0.05126429593656212
myLog is %s microseconds --- 4.137887543998659
easy is %s microseconds --- 0.10356121498625726
brute is %s microseconds --- 5.254867412033491
log2_approx is %s microseconds --- 3.81522585300263
log2 is %s microseconds --- 1.7966924259671941
power_of_2 is %s microseconds --- 0.1572157460032031
log2_fast is %s microseconds --- 0.21886748599354178