az AMD Software Optimization Guide for AMD64 Processors c. kiadvanyaban van egy marha jo algoritmus* (biztos mashol is irjak, de en konkretan ott talalkoztam vele), ami azon alapszik, hogy elso korben ket bitenkent vegigszalad num-on, leszamolja, hogy a kettes bitcsoportokban hany 1-es bit van, majd negyesevel megy vegig a biteken, azokat is megszamolja, aztan nyolcasaval, stb. stb. igazabol zsenialis! :)
valahogy igy nez ki 8 bitre:
(1), a = num - ((num >> 1) & 0x55);
(2), b = (a & 0x33) + ((a >> 2) & 0x33);
(3), c = (b & 0x0F) + (b >> 4);
ezt igy ranezesre meg szerintem a foldon senki nem ertette meg, szoval egy pelda:
legyen pl.: num = 0b01 10 11 01
(1) utan: a = 0b01 01 10 01 (azaz num-ban 1 + 1 + 2 + 1 bit van 1-ben)
(2) utan: b = 0b0010 0011 (azaz num-ban 2 + 3 bit van 1-ben)
(3) utan: c = 0b00000101 (es tenyleg!)
termeszetesen helyben is mukodik az algoritmus (azaz a, b es c helyere is nyugodtan lehet num-ot irni), csak igy talan erthetobb. 32 es 64 bit megszamolasara is egyszeruen bovitheto, ha megerti az ember, hogy hogyan mukodik.
8 bit leszamolasa eseten biztosan lassabb, mint a LUT-os megoldas, de az algoritmus lepesszama O(log(n))-el aranyos - tisztabb, szarazabb, biztonsagosabb erzes. 32 bites szamokkal mar pl. csunyan elveri a tobbi megoldast.
teszt:
LUT-os megoldas, az egyszeruseg kedveert 32bites valtozoban levo biteket 8 bites "szeletenkent" szamoljuk le:
#include...
unsigned char bitnum[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
unsigned char bitcnt8(unsigned char num) {
return (bitnum[num & 0x0F] + bitnum[num >> 4]);
}
unsigned char bitcnt16(unsigned int num) {
return(bitcnt8(num & 0xFF) + bitcnt8(num >> 8));
}
unsigned char bitcnt32(unsigned int num) {
return(bitcnt16(num & 0xFFFF) + bitcnt16(num >> 16));
}
int main() {
unsigned int cnt;
long x = 0;
for (cnt = 0; cnt < 1000000000; cnt++) {
x += bitcnt32(cnt);
}
printf("%d\n",x);
return 0;
}
eredmenyek:
user@ubuntu:~$ gcc a.c -O1
user@ubuntu:~$ time ./a.out
1962026240
real 0m30.640s
user 0m30.302s
sys 0m0.076s
a fenti kod megvalositasa:
#include...
unsigned char bitcnt32(unsigned int num) {
num = num - ((num >> 1) & 0x55555555);
num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
num = (num + (num >> 4)) & 0x0F0F0F0F;
num = (num * 0x01010101) >> 24;
return(num);
}
int main() {
unsigned int cnt;
long x = 0;
for (cnt = 0; cnt < 1000000000; cnt++) {
x += bitcnt32(cnt);
}
printf("%d\n",x);
return 0;
}
eredmenyek:
user@ubuntu:~$ gcc b.c -O1
user@ubuntu:~$ time ./a.out
sizeof(char)=1
1962026240
real 0m8.606s
user 0m8.537s
sys 0m0.020s
(a forditas azért ment -O1-el, mert -O2-nel mindent kioptimalizalt a gcc)
*forras: http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs… - 179. oldal (illetve a pdf oldalszamozasa szerint a 195.)