0

I am looking for a formula which will tell me how many times I must divide a number $(n)$ by $2$ until its value is less than or equal to $1$.

For example, for $n=30$ $(30,15,7.5,3.25,1.75,0.875)$ would yield $5$ (number of times divided by $2$).

How can I express this as a formula?

Lemmon
  • 1,234
TSG
  • 111

2 Answers2

1

If you do not have the ceil function at your disposal, you can use the following formula : $$m=\begin{cases}\left\lfloor\dfrac{\ln n}{\ln2}\right\rfloor+1\quad\text{ if }\;n\;\text{ is not a power of }2\\\left\lfloor\dfrac{\ln n}{\ln2}\right\rfloor\qquad\;\text{ if }\;n\;\text{ is a power of }2\end{cases}$$

which does not require $\;\log_2x\;$ function but just the natural logarithm.

In other words :

if $\;\left\lfloor\dfrac{\ln n}{\ln 2}\right\rfloor=\dfrac{\ln n}{\ln 2}\;,\;$ then

$m=\left\lfloor\dfrac{\ln n}{\ln 2}\right\rfloor\quad$ otherwise $\quad m=\left\lfloor\dfrac{\ln n}{\ln 2}\right\rfloor+1\;.$

The symbol $\lfloor x\rfloor$ is the floor function and means "the greatest integer less than or equal to $x$". Programming languages have the floor function.

Angelo
  • 12,328
  • I tried this in excel and it seems to work. (Not sure why this is downvoted). I didn't test the case if n is a power of 2. It seems like a lot of overhead to test that. Is there a single formula that doesn't need a test like that? – TSG Nov 13 '22 at 23:55
  • @TSG, if you know that my answer is correct, you can upvote it by clicking on the arrow up icon. Obviously there exists a single formula that is $\lceil\log_2 n\rceil$ but not all programming languages have the ceil function, for that reason I wrote another formula. Moreover my formula just requires the natural logarithm and the floor function. You can test if a number $n$ is a power of $2$ by checking that $\left\lfloor\dfrac{\ln n}{\ln 2}\right\rfloor=\dfrac{\ln n}{\ln 2}.$ – Angelo Nov 14 '22 at 07:04
  • I would perhaps mention that $\lceil x\rceil=-\lfloor-x\rfloor$ for those who have floor but not ceil. –  Nov 14 '22 at 09:18
  • @StinkingBishop, you are completely right, we can also use the formula $\lceil x\rceil=-\lfloor -x\rfloor$. Thank you very much for having pointed it out. – Angelo Nov 14 '22 at 12:21
0

The formula is $\lceil\log_2 n\rceil$, the symbol $\lceil x\rceil$ meaning "the smallest integer greater or equal to $x$". (Programming languages often have a ceil function.)

This is because, if $m=\lceil\log_2n\rceil$, then $m-1\lt\log_2n\le m$, i.e. $2^{m-1}\lt n\le 2^m$ i.e. $\frac{n}{2^m}\le 1\lt \frac{n}{2^{m-1}}$ which means that $m-1$ halvings isn't enough to bring $n$ to $1$ (or under), but $m$ halvings is.

Update: If your platform does not support $\lceil x\rceil$ but it supports $\lfloor x\rfloor$, with the meaning "the largest integer less or equal than $x$" (often known as the floor function), then recall that $\lceil x\rceil=-\lfloor-x\rfloor$, i.e. the formula becomes $-\lfloor-\log_2 n\rfloor$. Make sure that your implementation of $\lfloor x\rfloor$ works correctly for the negative numbers, e.g. $\lfloor -0.5\rfloor=-1$.