Mail Archives: djgpp/1999/08/14/02:52:18
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/
- Raw text -