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

by RukiaKuchiki   Last Updated April 15, 2019 11:20 AM - source

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?

Tags :