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?

(In reply to Solution by Charlie)

Dividing a binary number by two and taking the integer value is in fact throwing away the rightmost bit.

When this bit is a zero, then the subtraction from the new value of the original value gives the same new value.
Example:
14 1110
 7  111
1110-111=111 (again 7)
So, as long as its a zero at the end of the binary number, the result of the the subtraction between the original number (14) and the new value (7) is the same as the result of the subtraction of the new value and zero.  Nothing changes: it is in fact the same problem all over, but now with a smaller value.

When the rightmost bit is a one, then consider this number as being the sum of an even number + 1.  The even number has a zero on the rightmost bit and acts as above.  The remaining one gets lost in the 'taking the integer part', nothing is left from it to be deducted from the original value.  So the original value is now one up.
This happens for every one, and the algorithm is counting 1's.

Posted by Hugo on 2005-01-14 18:27:09