From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16917 invoked by alias); 27 Apr 2002 18:58:31 -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 16910 invoked from network); 27 Apr 2002 18:58:29 -0000 Received: from unknown (HELO mail.oek.dk) (195.215.62.2) by sources.redhat.com with SMTP; 27 Apr 2002 18:58:29 -0000 Received: from k403b.oek.dk ([10.211.4.26] helo=yahoo.com) by mail.oek.dk with esmtp (Exim 3.12 #1 (Debian)) id 171XOu-0001IF-00 for ; Sat, 27 Apr 2002 20:58:28 +0200 Message-ID: <3CCAF4CF.6090406@yahoo.com> Date: Sat, 27 Apr 2002 12:44:00 -0000 From: David Rasmussen User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.9) Gecko/20020412 Debian/0.9.9-6 MIME-Version: 1.0 To: gcc@gcc.gnu.org Subject: Re: Number of 1's in 64 bit number...[don't read if not interested in algos/math...] Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-SW-Source: 2002-04/txt/msg01496.txt.bz2 I'm amazed to read all these suggestions. The problem is old and wellknown. It is usually called Population Count or PopCount. It is used in several situations, but the use I know best is from bitboard-based chess programs. Do a search of "chess bitboard" in google, and read about. The lookup-table is the usual implementation if potability is required. There are usually faster methods on a given platform, and some CPU's have this as a native instruction. In chess, the board is often relatively sparse and the following implementation is better overall than the lookup-table for such programs. It loops one time for each 1-bit: int PopCount(unsigned long long bitboard) { int count = 0; while(bitboard) { ++count; bitboard &= bitboard - 1; } return count; }