[logica] bits tellen

[ajslaghu]

Goedemorgen,


ik wil het aantal bits in een byte nou ja , unsigned long tellen;

Dus als ik het volgende bitword heb:
0000000011111111000000000000000000000000000000000000000000000b;
Moet het antwoord 8 zijn;

Oja, ik weet hoe ik een for loop schrijf alleen ik heb als dit mogelijk is i.v.m. performance een logische & ~^ | operatie want het moet allemaal nogal snel gaan.

[.oisyn]

je weet hoe je een bepaalde bit kunt testen? Dan kun je toch ook gewoon met een loopje alle bits afgaan en ze testen?

[Verwijderd]

Voor 8 bit :
v = (v & 0x55) + ((v >> 1) & 0x55);
v = (v & 0x33) + ((v >> 2) & 0x33);
return (v & 0x0f) + ((v >> 4) & 0x0f);


voor 32 bit integer:
#define g31 0x49249249ul // = 0100_1001_0010_0100_1001_0010_0100_1001
#define g32 0x381c0e07ul // = 0011_1000_0001_1100_0000_1110_0000_0111

v = (v & g31) + ((v >> 1) & g31) + ((v >> 2) & g31);
v = ((v + (v >> 3)) & g32) + ((v >> 6) & g32);
return (v + (v >> 9) + (v >> 18) + (v >> 27)) & 0x3f;


Welkom in de wereld van de bit-trucs

[ajslaghu]

het probleem is dat als ik een for loop doe dat er een stop conditie is die getest moet worden, en daar hebben we effe geen tijd voor.
De CPU probeert uitereerd vooruit te werken door haar pipelines maar overspelbaar gedrag heeft ze een hekel aan want dan kan ze niet vooruit werken.

[ Voor 1% gewijzigd door ajslaghu op 20-02-2003 11:19 . Reden: typo ]

[ajslaghu]

Wow led dit soort shit bedoel ik. Kan je ook uitleggen hoe het werkt zodat ik het kan omzetten naar unsigned 64's?

[Verwijderd]

zie bv. http://www-db.stanford.edu/~manku/bitcount.html

[madwizard]

Nog wat pagina's:
Population count of a 32-bit register (met uitleg), Source code for low level binary functions (van alles en nog wat).
In AMD's x86 code optimization guide (22007) staan ook een aantal geoptimaliseerde versies (onder andere een MMX versie voor 64-bits integers)