From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-return-50637-listarch-gcc=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 16977 invoked by alias); 25 Apr 2002 06:08:29 -0000
Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Archive: <http://gcc.gnu.org/ml/gcc/>
List-Post: <mailto:gcc@gcc.gnu.org>
List-Help: <http://gcc.gnu.org/ml/>
Sender: gcc-owner@gcc.gnu.org
Received: (qmail 16832 invoked from network); 25 Apr 2002 06:08:00 -0000
Received: from unknown (HELO msrvr.indofuji.soft.net) (164.164.95.115)
  by sources.redhat.com with SMTP; 25 Apr 2002 06:08:00 -0000
Received: (from Jaswant [192.168.1.66])
 by msrvr.indofuji.soft.net (NAVIEG 2.1 bld 63) with SMTP id M2002042511271002855
 ; Thu, 25 Apr 2002 11:27:10 +0530
Message-ID: <077b01c1ec20$3a0fd7f0$4201a8c0@indofuji.soft.net>
From: "Jaswant" <jaswant@indofuji.soft.net>
To: "Vivek Srivastava" <u2000159@cs.unipune.ernet.in>
Cc: <gcc-help@gcc.gnu.org>,
	<gcc@gcc.gnu.org>
References: <Pine.LNX.4.33.0204251050020.14499-100000@dogmatix.cs.unipune.ernet.in>
Subject: Re: Number of 1's in 64 bit number...[don't read if not interested in algos/math...]
Date: Wed, 24 Apr 2002 23:51:00 -0000
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700
X-SW-Source: 2002-04/txt/msg01289.txt.bz2

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