# How many times can you halve a number?

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$.

-

## migrated from cs.stackexchange.comMay 5 '12 at 20:42

This question came from our site for students, researchers and practitioners of computer science.

How does this question relate to relational algebra? – sepp2k Apr 8 '12 at 6:36
it's a fair question for cs, but heavy overlap with math – Joe Apr 8 '12 at 7:26
This should be on math.se – Ran G. Apr 8 '12 at 8:57
Voted to close as off-topic. While important in a sense, the question is middle school mathematics material, not computer science. – Raphael Apr 8 '12 at 9:31
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. – Alex ten Brink Apr 8 '12 at 9:51

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.

-

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

-
Excellent, thank you. – Char Apr 8 '12 at 15:09