9
$\begingroup$

Is there an formula stating the number of times you would have to halve a number to reduce it to some value less than or equal to $1$?

For example, for $6$ it takes three halvings: $6/2=3$, $\ 3/2=1.5$, $\ 1.5/2=0.75$.

Also, is there a representation using the floor function in conjunction?

For example, for $6$ it takes two halvings if we round each intermediate result down: $\lfloor 6/2\rfloor=3$, $\ \lfloor 3/2\rfloor=1$.

  • 4
    This is purely a math question, with no link to Computer Science. That Discrete Mathematics is often important for Computer Science does not mean every Discrete Mathematics question is on-topic here. Voted to close as off-topic.2012-04-08

2 Answers 2

14

Is there an equation stating the number of times you would have to half a number to reduce it to some value less than or equal to 1.

That would be the logarithm to base 2 rounded up to the next integer.

Also, is there a representation using the floor function in conjunction?

That would be the logarithm to base 2 rounded down.

7

Operation of dividing by 2 and flooring is same as bit shifting to right (>>).

You have to right shift $\lfloor \lg N\rfloor$ times to get value 1.

Because there are $\lfloor \lg N\rfloor + 1$ bits in binary representation of $N$.

e.g.

6 = 110  3 = 11  1 = 1 
  • 2
    Excellent, thank you.2012-04-08