Whadduzitdo? (Posted on 2005-01-14)

let S and D = N
repeat 
    let D = ⌊D/2⌋
    subtract D from S
until D=0
produce S as the result

	Submitted by e.g.
Rating: 3.7143 (7 votes)
Solution:	(Hide)
This algorithm calculates the number of ones in the binary representation of N. It's easy to see that if we start with 2N, we get the same result as starting with N, while if we start with 2N+1, the result is 1 more than if we start with N. Since starting with N=1 produces 1, the result follows. Check http://math.ucsd.edu/~mathclub/games/brainteaser-archive/counting.html for another proof.

	Subject	Author	Date
	Puzzle Solution	K Sengupta	2022-09-10 03:21:36
	Solution	Praneeth	2007-07-31 12:59:13
	very good, love the algorithmic view.	chris	2005-02-26 06:53:51
	additionally	sjh182	2005-01-20 06:53:59
	Solution	Larry	2005-01-14 23:42:34
	Independent Solution	Tristan	2005-01-14 23:00:39
	My thoughts on why the algorihm works	Hugo	2005-01-14 18:27:09
	Recursive solution	Federico Kereki	2005-01-14 17:33:10
	Solution	Charlie	2005-01-14 16:44:14
	An implementation (with results--a Hint--so look only if you want the hint)	Charlie	2005-01-14 15:16:49