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

["Jaswant" <jaswant at indofuji dot soft dot net>]

may be preeti is looking for something like algo below which finds 1's in 36
bit number:

//To count the ones in a 36-bit word:
unsigned count_ones(unsigned36 a)
{
  a = a - (a>>1 & 0333333333333);
  a = a - (a>>1 & 0333333333333);

  // Each octal digit is replaced by number of 1's in it

  a = ((a>>3) + a) & 0070707070707;
  return a % 63;    // casting out 63's
}


----- Original Message -----
From: "Vivek Srivastava" <u2000159@cs.unipune.ernet.in>
To: "Preeti Aira" <ms_preeti@hotmail.com>
Cc: <gcc-help@gcc.gnu.org>; <gcc@gcc.gnu.org>
Sent: Thursday, April 25, 2002 11:06 AM
Subject: Re: Number of 1's in 64 bit number...[don't read if not interested
in algos/math...]


> 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
>
>