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 nonprogrammers: 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. (1916=3.) What's the result?
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, 1000111 is 1, as is 1000000111111 and
101, etc. Therefore, the resulting S will be the sum of the
digits of N, when N is in binary form.

Posted by Tristan
on 20050114 23:00:39 