0

I want to know that is it possible to tell directly the number of steps to reaching 0 from a given number given that a number can be reduce to its half in each step. For Example :

9 step 1:9/2=4 (Integer)

step 2:4/2=2

step 3:2/2=1

step 4:1/2=0

So number of steps 4.

IS there any Direct way for this ????

Lalit Verma
  • 1
  • 1
    Do you know of something called the natural logarithm? If not, read it up. The answer to : how many steps does $n$ take to reach zero, is $\Big\lceil\frac{\ln n}{\ln 2}\Big\rceil$, whenever the argument is not an integer, and $\Big\lceil\frac{\ln n}{\ln 2}\Big\rceil$ when the argument is an integer. – Sarvesh Ravichandran Iyer Sep 20 '16 at 11:28
  • Thanks. I know Log() but did not know about this property :) – Lalit Verma Sep 20 '16 at 11:34
  • 1
    Please, still check the above formula. It may have small mistakes, but surely the answer is along these lines. – Sarvesh Ravichandran Iyer Sep 20 '16 at 11:35
  • Two small corrections to the formula: if $n$ is negative, then you need to take $\ln |n|$. And when $n$ is a power of $2$, You need to add one to the answer. (Example: $\frac{\ln 2 }{ \ln 2} = 1$, but to get from $2$ to $0$ by integer division requires two steps.) So a revised answer is $1 + \Big\lfloor\frac{\ln |n|}{\ln 2}\Big\rfloor$. – John Hughes Sep 20 '16 at 11:44

1 Answers1

1

Usually to know how many steps you need to reduce a number to $1$ by dividing by $2$ calculate $log_2^a$, where $a$ is your target number. As the answer should be integer take $\lfloor log_2^a \rfloor$ (round down). Finally add one as you want the number to reach $0$ not $1$.

Sargsyan Grigor
  • 292