Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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