Finding the greatest power of $2$ less than or equal to a given number

Question

I'm looking for an algorithm, or better yet formula, that I can use with a piece of paper and a pen to find the greatest power of $2$ less than or equal to a given number.

Suppose I have the number $15285$, what's the easiest way to find out what the greatest integer power of $2$ that is less than or equal to that number without using a calculator? For example, for the number $9$, the maximum power of $2$ is $3$, because $2^4>9\geq 2^3$

Answer 1

The following method is essentially binary expansion, discarding some information along the way.

If $n$ is even, divide by $2$;
If $n$ is odd, subtract $1$ and divide by $2$.
Repeat until you get $1$.

The number of steps is the exponent you are looking for.

Examples
$n=9$: $\to4\to2\to1$, three steps
$n=15$: $\to7\to3\to1$, three steps
$n=16$: $\to8\to4\to2\to1$, four steps $n=15285$: $\to7642\to3821\to1910\to955\to477\to238\to119\to59\to29\to14\to7\to3\to1$, 13 steps

Using a calculator, one can do $\left\lfloor\log_2n\right\rfloor$ (or just take $\log_2n$ and ignore the fractional part).

Answer 2

If we're talking divisibility, your number is odd so the only power of two that divides into this number is $1$. The thing is that this is a boring answer, but it's the only one.

But if we're talking about the largest power of two smaller than this number, I usually do this by brute force. Try factoring the number and obtain some estimates with powers of two.

Answer 3

Floor ( logarithm to the base 2 of the given number).

Answer 4

The easiest way is to just divide by 2, ignore remainder, repeat.

But as $x = 2^{\log_2 x}$ and $2^{10} = 1024 \approx 10^3$ a way of guessing could be $\log_2 x \approx \frac 13 \log_{10} x$:

Well, I'll show with an example:

$23,536,286,290$

$23,536,286,290 \approx 2.3 * 10^{10} = 23 * 10^{9}$

$= 23 * 1000^3 < 23 * 1024^3 = 23 * 2^{30}$

$2^4 < 23 < 2^5$

So the power should be about $34$ maybe less. Less than $35$.

To determine if that is so:

So $2^{30} = 1024^3 = 1,000,000,000 + 3*24*1000,000 + 3*24^2*1000 + 24^3$

$\approx 1,072,xxx,xxx$. So $2^{34} \approx 16* 1,072,xxx,xxx \approx 1,7xx,xxx,xxx < 23,536,286,290 < 2*1,7xx,xxx,xxx \approx 3,4xx,xxx,xxx \approx 2^{35}$ so the answer is $2^{34}$.

====

Actually to make the above answer clearer:

$xyzabcde$ has $n + 1$ digits. Write as $x.y * 10^n$. Try to eyeball $x.y = 2^k$ The highest power is about $n*10/3 + k$

Double check by writing as $xy * 10^{n- 1}$. Try to eyball $xy = w^j$. The highest power is about $(n-1)*10/3 + j$.

Choose the for which eyeballing $x.y = 2^k$ or $xy = 2^j$ seem to have less range of error.

Answer 5

Many calculators can give you the answer for a given number $n$ the following way:

Example:$$\log_2(77869)=16.2487614787$$Therefore the answer in this case is $16$; in fact,

$$2^{16}=65536\lt77869\lt2^{17}=131072$$