From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-return-50690-listarch-gcc=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 22550 invoked by alias); 25 Apr 2002 18:13:25 -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 22517 invoked from network); 25 Apr 2002 18:13:21 -0000
Received: from unknown (HELO gra-vd1.iram.es) (150.214.224.250)
  by sources.redhat.com with SMTP; 25 Apr 2002 18:13:21 -0000
Received: from iram.es (localhost [127.0.0.1])
	by gra-vd1.iram.es (8.11.2/8.11.2/SuSE Linux 8.11.1-0.5) with ESMTP id g3PIDHh12411;
	Thu, 25 Apr 2002 20:13:17 +0200
Message-ID: <3CC8473D.8030101@iram.es>
Date: Thu, 25 Apr 2002 11:24:00 -0000
From: Gabriel Paubert <paubert@iram.es>
User-Agent: Mozilla/5.0 (X11; U; Linux ppc; en-US; rv:0.9.5) Gecko/20011016
X-Accept-Language: en-us
MIME-Version: 1.0
To: Nathan Sidwell <nathan@acm.org>
CC: gcc@gcc.gnu.org
Subject: Re: Number of 1's in 64 bit number...[don't read if not interested in           algos/math...]
References: <Pine.SOL.4.43.0204251302420.27320-100000@ivy.ee.princeton.edu> <3CC83D87.506F1499@acm.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable
X-SW-Source: 2002-04/txt/msg01342.txt.bz2

Nathan Sidwell wrote:

> Wei Qin wrote:
>=20
>>First, I see only 32 bits being counted. The top 32 bits seems missing.
>>Second, this is a very slow implementation. A faster one can be
>>implemented through table lookup. It takes no masking, no branching.
>>
>>
> I suspect something like...
> int bitson (unsigned long x)
> {=20=20=20
>   x =3D (x & 0x55555555) + ((x >> 1) & 0x55555555);


Actually the most clever way of implementing
that step that I know is:

x -=3D (x>>1)&0x55555555;

This happens to give the correct result for each
pair of bits.

Credit where credit is due: I found this trick on
IBM=B4s website in their PPC compiler writer=B4s guide.

	Regards,
	Gabriel.