From: DavMac AT iname DOT com (Davin McCall)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Bit counting?
Date: Sat, 14 Aug 1999 03:28:51 GMT
Organization: Monash Uni
Lines: 80
Distribution: world
Message-ID: <37b4e020.2582291@newsserver.cc.monash.edu.au>
References: <37B45836 DOT EAD7C82D AT swipnet DOT se> <37B48ABE DOT 110D2C13 AT intel DOT com> <37B4D8BC DOT 6465 AT ns DOT sympatico DOT ca>
NNTP-Posting-Host: damcc5.halls.monash.edu.au
X-Trace: towncrier.cc.monash.edu.au 934601273 11963 130.194.198.138 (14 Aug 1999 03:27:53 GMT)
X-Complaints-To: abuse AT monash DOT edu DOT au
NNTP-Posting-Date: 14 Aug 1999 03:27:53 GMT
X-Newsreader: Forte Free Agent 1.1/32.230
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

I don't think modulo is *that* slow, especially on newer processors.
An alternative way to do it is (this is quite complicated)

Mask of every 2nd bit and store the result (say in "masked1")
Mask of every *other* bit and store the result (masked2)

eg: (written in "not-exactly-C"):

    mask1 = value & 01010101010101b;
    mask2 = value & 10101010101010b;

Then shift mask2 right one:

    mask2 >>= 1;

Now, The total number of bits in mask1 and mask2 is equal to the total
number of bits in value. More importantly, mask1 and mask2 can each be
seen as a sequence of two bit numbers (MSB 0) whose total is the
number of set bits. Now if we do:

    tempvalue = mask1 + mask2;

We get tempvalue, a single variable containing a sequence of two bit
numbers, the total of which is the total number of bits in value. On
this value we use the same method with a slightly different mask:

    mask1 = tempvalue & 0011001100110011b;
    mask2 = (tempvalue & 1100110011001100b) >> 2;

Now mask1 and mask2 each contain a sequence of four bit numbers (two
MSBs 0) whose total value is the number of bits set in value. In the
same manner as before:

    tempvalue = mask1 + mask2;

Now, tempvalue contains a sequence of four bit numbers whose total
value is the number of bits set in value.

The process can be repeated to get a sequence of 8 bit values, and
continued until tempvalue contains a sequence of N-bit values where N
is the number of bits in value. In this case, tempvalue contains only
one number: the total number of bits in value.

Davin.


On Fri, 13 Aug 1999 23:47:24 -0300, Klaas <klaas AT ns DOT sympatico DOT ca>
wrote:

>Kurt Alstrup wrote:
>> 
>> Try this little function, I guess it may gain if written in assembly
>> though ..
>> 
>> /*
>>  *      Ones
>>  *
>>  * This magic counts the number of bits in one longword
>>  */
>> 
>> int
>> Ones(unsigned long mask)
>> {
>>   register unsigned long y;
>> 
>>   y = (mask >> 1) & 033333333333;
>>   y = mask - y - ((y >>1) & 033333333333);
>>   return (int) (((y + (y >> 3)) & 030707070707) % 077);
>> }
>> 
>> Regards,
>> Kurt Alstrup
>
>Doesn't the modulo make it rather slow?
>
>-Mike

__________________________________________________________
       *** davmac - sharkin'!! davmac AT iname DOT com ***
my programming page: http://yoyo.cc.monash.edu.au/~davmac/