bits in 64 integer zaehlen ...

hi,

kann mir jemand vielleicht sagen, wie der folgende algorithmus zum zaehlen von bits in einer 32 bit zahl geaendert werden muss, damit es auch fuer ne 64 bit zahl funzt

int bitcount(unsigned int n)                          
 {
    register unsigned int tmp;

    tmp = n - ((n >> 1) & 033333333333)
            - ((n >> 2) & 011111111111);
    return ((tmp + (tmp >> 3)) & 030707070707) % 63;
 }

es muesste soweit ich weiss die letzte zeile geaendert werden:
modulo 1023 statt 63.
aber zudem der ausdruck davor auch.
obiger ausdruck vor dem % 63 zaehlt jeweils die bitanzahl in zwei benachbarten 3er bitgruppen.
Fuer 64 bit-zahl muessten dies drei 3'er gruppen sein.
habe aber keine idee wie.

der algorithmus ist uebrigens entnommen aus:
[url]
http://www-db.stanford.edu/~manku/bitcount/bitcount.html
[/url]

vielen danke.

Meep Meep

hi

warum nicht die 64 bit in 2 x 32 bit aufteilen und dann berechnen ?

Meep Meep

camper

wenn ich das richtig verstehe, dürfte man dann nicht mehr nur octale digits verwenden, denn die summe der bits eines triples könnte ja 9 betragen, was zum überlauf führte. ich würde lieber nibbles zusammenflanschen und dann mit modulo 255 arbeiten (völlig ungetestet):

int bitcount(u64 n)                          
{
    n = n - ( (n >> 1) & 0x7777777777777777 )
          - ( (n >> 2) & 0x3333333333333333 )
          - ( (n >> 3) & 0x1111111111111111 );
    return ( ( n + n >> 4 ) & 0x0f0f0f0f0f0f0f0f ) % 255;
}

andere varianten sind möglich. im prinzip ein lustiger algorithmus, dummerweise macht das modulo die performance zunichte (bis auf ein paar spezielle prozessoren, die modulo 2^n-1 sehr schnell berechnen können...).