From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-return-50693-listarch-gcc=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 27059 invoked by alias); 25 Apr 2002 19:15:13 -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 26980 invoked from network); 25 Apr 2002 19:15:07 -0000
Received: from unknown (HELO clausfischer.com) (216.4.73.9)
  by sources.redhat.com with SMTP; 25 Apr 2002 19:15:07 -0000
Received: from boltzmann.strudlhofstiege (localhost [127.0.0.1])
	by clausfischer.com (Postfix) with ESMTP id 8EBD5BAF6
	for <gcc@gcc.gnu.org>; Thu, 25 Apr 2002 20:57:07 +0200 (CEST)
Received: by boltzmann.strudlhofstiege (Postfix, from userid 1000)
	id 51B6A1680A; Thu, 25 Apr 2002 21:15:06 +0200 (CEST)
Date: Thu, 25 Apr 2002 12:23:00 -0000
From: Claus Fischer <claus.fischer@clausfischer.com>
To: gcc@gcc.gnu.org
Subject: [OT] Number of 1's in 64 bit number
Message-ID: <20020425211506.A8532@clausfischer.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.2.5i
X-SW-Source: 2002-04/txt/msg01345.txt.bz2


Off-topic though interesting. I wonder if there's a generic place
to find collections of such kind of algorithms.

The proposed solution

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

is buggy for octal digits of 3 and 7.
A working modification of the 36-bit solution seems to be

unsigned long count_ones(unsigned36 a)
{
  /* Each octal digit is replaced by number of 1's in it */
  a = a - (a>>1 & 0333333333333) - (a>>2 & 0111111111111);

  /* Combine groups of two octal digits each */
  a = ((a>>3) + a) & 0070707070707;

  /* Add up, using the fact that 64 == 1 (mod 63) */
  return a % 63;
}

But this will only work if there are less than 63 bits set
in the number, so it's not generic for 64 bit numbers either.

For 64 bits use Nathan's solution.

Claus

-- 
Claus Fischer <claus.fischer@clausfischer.com>
http://www.clausfischer.com/