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?
$\begingroup$
$\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
Add a comment
|
$\begingroup$
$\endgroup$
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).
