# 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 : def log2(n):
...:     i = 0
...:     while n > 1:
...:         n >>= 1
...:         i += 1
...:     return i

In : log2(33554432)
Out: 25

In : import math

In : math.log2(33554432)
Out: 25.0

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

In : %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?

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
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
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
```