Re: Number of 1's in 64 bit number...[don't read if not interestedin algos/math...]

[Vivek Srivastava <u2000159 at cs dot unipune dot ernet dot in>]

Hi Preeti,

On Thu, 25 Apr 2002, Preeti Aira wrote:
> Can any body give me the algo for finding number of 1's  (set bits) in a 64 
> bit number. Algo with out any loop or recurson.  Should be a reasonably 
> efficient and small and giving result in fixed time.

I don't know why do you ask for an algo without any loops or recursion. As 
far as I can see, it cannot be done without them. So if you're ready to 
incorporate them, here's one algo. It's probably the most efficient one 
possible because it gives the result in O(n) time, where 'n' is the number 
of 1 bits in the number. (Doesn't depend on the size of the number.) i.e. 
for both 10110000 and 0000101100000000, it will tell you that there are 3 
1's in just 3 steps.

Here's the algo:

	Let x be the given number.
	count <-- 0
	while (x > 0)
	do
	    	x <-- x AND (x - 1)
		count <-- count + 1


At the end of this loop, 'count' is the required answer. (Here, AND is the 
bitwise 'and' operator.)

Hope that helps.

Vivek

-- 
Vivek Srivastava
MCA II year
Department of Computer Science
University of Pune