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 Solution | Comment 2 of 9 |
(In reply to An implementation (with results--a Hint--so look only if you want the hint) by Charlie)

Note that when the program is run, powers of two result in S = 1, while large values occur just before the power of two.  This suggests the algorithm is counting the 1 bits in the binary representation of the number N.  This is also suggested by the continual division by 2, although it's not obvious why the algorithm works exactly, by subtracting these quotients from S.

The following program incorporates a conventional conversion of numbers to binary, counting 1 bits as it goes along, as well as implementing the algorithm of the puzzle.  The count of 1 bits always matches the result of the puzzle algorithm, confirming that that is in fact what it does.

DECLARE FUNCTION bi$ (x!)
DIM SHARED tot
CLS
FOR n = 1 TO 40
 s = n: d = n
 DO
   d = INT(d / 2)
   s = s - d
 LOOP UNTIL d = 0
 PRINT USING "## & ## ## "; n; RIGHT$("          " + bi$(n), 10); s; tot
NEXT

FUNCTION bi$ (x)
 b$ = ""
 tot = 0
 v = x
 DO
  q = v \ 2
  r = v MOD 2
  tot = tot + r
  v = q
  b$ = LTRIM$(STR$(r) + b$)
 LOOP UNTIL q = 0
 bi$ = b$
END FUNCTION

Results:

 1          1  1  1
 2         10  1  1
 3         11  2  2
 4        100  1  1
 5        101  2  2
 6        110  2  2
 7        111  3  3
 8       1000  1  1
 9       1001  2  2
10       1010  2  2
11       1011  3  3
12       1100  2  2
13       1101  3  3
14       1110  3  3
15       1111  4  4
16      10000  1  1
17      10001  2  2
18      10010  2  2
19      10011  3  3
20      10100  2  2
21      10101  3  3
22      10110  3  3
23      10111  4  4
24      11000  2  2
25      11001  3  3
26      11010  3  3
27      11011  4  4
28      11100  3  3
29      11101  4  4
30      11110  4  4
31      11111  5  5
32     100000  1  1
33     100001  2  2
34     100010  2  2
35     100011  3  3
36     100100  2  2
37     100101  3  3
38     100110  3  3
39     100111  4  4
40     101000  2  2

 


  Posted by Charlie on 2005-01-14 16:44:14
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 (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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