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?

See The Solution Submitted by e.g.    
Rating: 3.7143 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Independent Solution | Comment 5 of 9 |
First, consider the numbers in binary system.  N might be, say, 11010 or 26 in decimal.  When D is halved and rounded down, it is like removing the last digit of the binary form.  So first it would become 1101, then 110, 11, 1, and 0.

This means that if there is a 1 in, say, the 4th digit from the right, a total of 111 will be subtracted from S before the one disappears.  Naturally, 1000-111 is 1, as is 1000000-111111 and 10-1, etc.  Therefore, the resulting S will be the sum of the digits of N, when N is in binary form.

  Posted by Tristan on 2005-01-14 23:00:39
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