From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 8069 invoked by alias); 25 Apr 2002 05:47:28 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 7980 invoked from network); 25 Apr 2002 05:47:25 -0000 Received: from unknown (HELO jivdhan.unipune.ernet.in) (196.1.114.31) by sources.redhat.com with SMTP; 25 Apr 2002 05:47:25 -0000 Received: from cs.unipune.ernet.in (cs.unipune.ernet.in [196.1.114.3]) by jivdhan.unipune.ernet.in (8.11.6/8.11.6) with ESMTP id g3P5lID06995; Thu, 25 Apr 2002 11:17:18 +0530 Received: from dogmatix.cs.unipune.ernet.in (dogmatix.cs.unipune.ernet.in [192.9.150.6]) by cs.unipune.ernet.in (8.11.6/8.11.2) with ESMTP id g3P5jOx15997; Thu, 25 Apr 2002 11:15:24 +0530 Received: from localhost (u2000159@localhost) by dogmatix.cs.unipune.ernet.in (8.11.6/8.11.6) with ESMTP id g3P5a5A15956; Thu, 25 Apr 2002 11:06:05 +0530 X-Authentication-Warning: dogmatix.cs.unipune.ernet.in: u2000159 owned process doing -bs Date: Wed, 24 Apr 2002 23:08:00 -0000 From: Vivek Srivastava To: Preeti Aira cc: , Subject: Re: Number of 1's in 64 bit number...[don't read if not interested in algos/math...] In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2002-04/txt/msg01288.txt.bz2 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