• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

math question - (divided by 2?)

 
Ranch Hand
Posts: 113
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is there a smart manner to determine how many times a given integer n number can be divided by two?

For example, 2 can be divided one time by 2.
Any odd number can't be divided by 2.
A number that is a power of 2 can be divided by two exactly log n ( 8 can be divided lg 8 = 3 times by two because 8 = 2^3).

But for the even numbers that are not a power of two, how do I say how many times they can be divided by two?

Thanks.
 
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you look at the number in binary, then this is determined by the number of zeroes at the end of a number. A number that ends in 1 is not divisible by 2, and for numbers that are divisible by 2, each division by 2 removes one of the trailing zeroes.

That's useful if a number is already in binary. Which is generally the case when you're programming. But if you, a human, are looking at a decimal number, then in order to convert to binary, you have to perform a series of divisions. So this trick isn't really any faster for answering your question. If you want to know how many times a number can be easily divided by two, the fastest way is probably to keep dividing by two until you get an odd number.

In Java, you can just use Integer.numberOfTrailingZeros().
 
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Determine how many times 2 goes into the final digit. (For example, if your number is 416, then 2 goes into 6 three times.)

Remove that last digit from the number and multiply by 5. (So 416 becomes 41, and 41 * 5 is 205.)

Add the results. (3 + 205 = 208.)
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yeah - that's much easier than simply dividing by two.
 
Bartender
Posts: 1849
15
Eclipse IDE Spring VI Editor Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

marc weber wrote:Determine how many times 2 goes into the final digit. (For example, if your number is 416, then 2 goes into 6 three times.)

Remove that last digit from the number and multiply by 5. (So 416 becomes 41, and 41 * 5 is 205.)

Add the results. (3 + 205 = 208.)





This looks like some sort of mathematical voo-doo. Where do you get the 5 from?

I see it works, but WHY???
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Removing the last digit of a number is like dividing by ten and losing any remainder. Removing the last digit and then multiplying by five is like dividing by ten and then multiplying by five, which is like multiplying by 5/10 or 1/2. Which is like dividing by two.

What about the lost remainder? Well, that was handled back at the beginning when we looked at the last digit and divided by two, then added the result back on at the end.

So for example:

123456 / 2 = (123450 + 6) / 2 = 123450 / 2 + 6 / 2 = (1234 * 5) + 6 / 2

Here you see everything but the last digit, times 5, plus the last digit, divided by two.
 
Janeice DelVecchio
Bartender
Posts: 1849
15
Eclipse IDE Spring VI Editor Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Holy crap.
 
Rancher
Posts: 4803
7
Mac OS X VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

marc weber wrote:Determine how many times 2 goes into the final digit. (For example, if your number is 416, then 2 goes into 6 three times.)
Remove that last digit from the number and multiply by 5.



Cute. But its a lot more work than just doing the division. So while its clever, I'm not sure its "smart" by any sensible criteria.

Even the "remove the last digit" is hard to do on a computer without doing the division by 10, which binary computers do not do well.

If your computer does not have an integer divide instruction, you could do a series of mask/test the lowest bit, and shift right, which is how the division is done in software on those machines.
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I figured it was meant as a joke.
 
marc weber
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I just took the original post to be asking for methods other than the straight-forward approach of dividing by 2. The example given (deriving the base 2 log of n, for cases in which n is a power of 2) doesn't seem any easier than simply dividing by 2.
 
Rancher
Posts: 152
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rod Bossini wrote:Is there a smart manner to determine how many times a given integer n number can be divided by two?



The answer is "infinite". Nowhere is it mentioned that the result of the division shouldn't be a fraction.
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Oh, please. The original post was pretty clear on this with its examples.
 
Teja Saab
Rancher
Posts: 152
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:Oh, please. The original post was pretty clear on this with its examples.



 
Ranch Hand
Posts: 1419
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Suppose you have a list of the powers of two:

2, 4, 8, 16, 32, 64, ....

So think of the problem as a binary search to determine the largest element of the list that is a factor of your number.

Initial endpoints are 2 and the largest element of the list that is smaller than your number.

Pick the power of 2 that is in the middle of your interval, and see whether it divides your number.
If no, then your new interval is your previous low value, and the power of two that is immediately to the left as your high value.
If yes, then the low end of your new interval is the number you just picked, and you keep the previous high end of your interval.
Repeat until your interval contains just one number.

This algorithm may be useful if the initial interval size (possible powers of 2) is very large.
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Frank: nice, that actually can be faster than the standard solution, depending on what we know about the range and distribution of input values. Good thinking.

Teja:

For example, 2 can be divided one time by 2.
Any odd number can't be divided by 2.


It's obvious that that Rod is talking about being evenly divisible. To say "Nowhere is it mentioned that the result of the division shouldn't be a fraction" is to completely ignore what Rod actually did say, which contradicts the possibility of fractional results. You might think it should have been phrased differently, but it's disingenuous to simply ignore it.
 
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
dividing by 2 is the left shift binary operation
For ex.:
8 = 1000 in the binary form
so, to divide by 2 we should shift it to left one time.
1000(8) >> 1 = 100(4)
100(4) >> 1 = 10(2)
10(2) >> 1 = 1(1)

so, we shift it tree times = (last_value_position_bit - 1) ;)
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Wow - it's almost as though if you look at the number in binary, the question is answered by the number of zeroes at the end of the number. How interesting.
 
Ranch Hand
Posts: 577
Tomcat Server Notepad Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is a simple program which does the job. Hope you are looking something like this, if not let us know.
Note: You can change the code so that variable n value is provided at the runtime.
 
Bartender
Posts: 2700
IntelliJ IDE Opera
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you for sharing but Mike gave the answer already. Not in a concrete way but with a great hint.
The best solution would probably be:
 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The logic where last n number of zeros are the times that number is divisible by 2. Are there some edge case in which it's not true?
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Not really. When using two's complement representation, it works for negative numbers as well.

Zero could be seen as an edge case because it can be divided an infinite number of times, but in practice it won't really lead to any problems. If you want to treat zero specially, you can do something like this:


Welcome to CodeRanch!
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
<pedantic mode on>

Any number can be divided by two exactly once - Once you divide (say) 32 by 2, you're left with 16.  you are no longer dividing 32 any more.

Any number can be divided by two an infinite number of times...you just start getting fractions.

Any number can be divided by two an infinite number of times.  32 / 2 = 16.  I can then do it again...32 / 2 = 16.  32 / 2 = 16.....

<end pedantic mode>
 
Rohan Shenoy
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have written a code with the logic of counting consecutive zeros as a number can be shifted any number of time. For example 0110 can be 1100, 1001, etc. so the number 1100 has max zeros at the end. So ans is 2. Also instead of 0110 I'm considering it as 01100110 (joined twice) to have start end together. Most test cases are passing. Only 2/14 test case failing. Since it's a competition I don't have input file too.
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rohan Shenoy wrote:. . . . Are there some edge case in which it's not true?

Yes. Of course there are. You can have a tri‑state bit (0, 1, −1) and work in ternary arithmetic.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic