Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

migrated from cs.stackexchange.com May 5 '12 at 20:42

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

1  
How does this question relate to relational algebra? –  sepp2k Apr 8 '12 at 6:36
1  
it's a fair question for cs, but heavy overlap with math –  Joe Apr 8 '12 at 7:26
2  
This should be on math.se –  Ran G. Apr 8 '12 at 8:57
1  
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
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. –  Alex ten Brink Apr 8 '12 at 9:51

2 Answers 2

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.

share|improve this answer

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
share|improve this answer
2  
Excellent, thank you. –  Char Apr 8 '12 at 15:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.