# Find the power of 2

Assume $$n=2^k$$, write an algorithm that can find $$k$$.

**log function is not allowed.

Is there an efficient way to find the power instead of multiplying by 2 until it equals $$n$$? What is the optimal efficiency?

• Compute $1,2,4,8,16,\ldots$ until you exceed $n$. – Yuval Filmus May 18 '20 at 11:28
• I’d allow the log function (which is base 10 or base e usually, depending on the language used), giving zero points if the answer is not correct in all cases. And not “assume n = 2^k” but ”verify that N = 2^k”. First test case would be n = 2^63-1. – gnasher729 May 18 '20 at 11:33
• It depends on the input range, whether it is bounded. And can k be negative? – TEMLIB May 18 '20 at 20:51
• And it can depend on implementation. If we assume a binary computer, finding k is finding first 1 in the binary, or, with standard floating point numbers, just picking the exponent field. – TEMLIB May 18 '20 at 20:55

Assuming arithmetic operations take constant time, you can compute it in $$O(\log \log n)$$ time.
Start with $$n_0=2$$ and iteratively compute $$n_i = n_{i-1} \cdot n_{i-1} = 2^{2^i}$$ until $$n_{i} > n$$.
The number of iterations is then $$\log \log n$$ and $$n_{i-1} = 2^{2^{i-1}} \le n < 2^{2^i} = n_i$$. At this point you can binary search for the right exponent among the $$2^i - 2^{i-1} = 2^{i-1} \le k$$ possible exponents. This takes time $$O(\log k) = O(\log \log n)$$ (exponentiation with a base of $$2$$ can usually be performed with a single left shift operation).