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 resultNote: ⌊
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?
(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 |
Solution
