1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Compute $1,2,4,8,16,\ldots$ until you exceed $n$. $\endgroup$ – Yuval Filmus May 18 '20 at 11:28
  • $\begingroup$ 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. $\endgroup$ – gnasher729 May 18 '20 at 11:33
  • $\begingroup$ It depends on the input range, whether it is bounded. And can k be negative? $\endgroup$ – TEMLIB May 18 '20 at 20:51
  • $\begingroup$ 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. $\endgroup$ – TEMLIB May 18 '20 at 20:55
6
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.