Compute $ \lceil{log_2(n)}\rceil $ through basic arithmetic operation

Question

first explain me my motivation:

I need to write a RAM program which compute $ \lceil{log_2(n)}\rceil $ for $ n \in \mathbb{N} $.

Idea

If I have $ n = $ "power of two" ( for example $ 8 = 2^3 $). I would say that we use the integer division DIV . So in every step in our loop we count the number of DIV $2$. So far so good. But it is obvious that not every number in $n \in \mathbb{N}$ is not a number of power of two.So how can I "fix" my loop? Someone told me that I have to consider MOD $2$ in every step and have to combine it with the bitwise OR, if I'm not mistaken. Can somebody can help me here?

Answer 1

Try the following algorithm

t = 9 #(starting value)
r = 0 #answer
while t > 1:
    t = ceil(t/2)
    r += 1
print(r)

This works because the ceiling iside the loop essentially pushes the number to next lowest power of 2. If ceiling does not count as basic airthematic operation you could replace it with $t = t/2+(t(mod (2)))$. I don't think bitwise OR is needed

for example, $t = 14, \log_214 \approx 3.8$ hence the answer should be $4$
$t = 14, r = 0$
$t = 7, r = 1$
$t = 4, r = 2$
$t = 2, r = 3$
$t = 1, r = 4$ (end since $t \le 1$)

Answer 2

You need the value $k$ such that $2^{k-1} < n \leq 2^k.$ So how about:

x = 1
t = 0
while x <= n:
   t +=1
   x = 2*x
print(t)