All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Whadduzitdo? (Posted on 2005-01-14) Difficulty: 4 of 5
Given positive, integer N, what does this algorithm produce?
let S and D = N
repeat 
    let D = ⌊D/2⌋
    subtract D from S
until D=0
produce S as the result
Note: ⌊x⌋ represents the integer part of x.

For non-programmers: start with a positive, integer number (say, 19). Divide it by 2, discarding remainders, until you get to 0. (In this case, you'd get 9, 4, 2, and 1.) Sum all the quotients. (9+4+2+1=16.) Subtract the sum from the original number. (19-16=3.) What's the result?

  Submitted by e.g.    
Rating: 3.7143 (7 votes)
Solution: (Hide)
This algorithm calculates the number of ones in the binary representation of N.

It's easy to see that if we start with 2N, we get the same result as starting with N, while if we start with 2N+1, the result is 1 more than if we start with N. Since starting with N=1 produces 1, the result follows.

Check http://math.ucsd.edu/~mathclub/games/brainteaser-archive/counting.html for another proof.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
SolutionSolutionPraneeth2007-07-31 12:59:13
Some Thoughtsvery good, love the algorithmic view.chris2005-02-26 06:53:51
Some Thoughtsadditionallysjh1822005-01-20 06:53:59
SolutionSolutionLarry2005-01-14 23:42:34
SolutionIndependent SolutionTristan2005-01-14 23:00:39
My thoughts on why the algorihm worksHugo2005-01-14 18:27:09
SolutionRecursive solutionFederico Kereki2005-01-14 17:33:10
SolutionSolutionCharlie2005-01-14 16:44:14
Hints/TipsAn implementation (with results--a Hint--so look only if you want the hint)Charlie2005-01-14 15:16:49
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2021 by Animus Pactum Consulting. All rights reserved. Privacy Information