@gary11: Po co operator trójargumentowy? int bit=0; do {bit+=val&1;} while(val>>=1); return bit; Chociaż muszę przyznać, że zmapowanie całego bajtu też jest spoko.
"Rozwiązanie ostateczne" jest nieoptymalne zarówno z punktu widzenia zapotrzebowania na pamięć jak i szybkości wykonania. Zdecydowanie najlepsze podejście to #3 (przesunięcie bitowe).
związanie ostateczne wymaga każdorazowo dostępu do pamięci na każde 8 bitów argumentu (pobranie z tablicy). Rozwiązanie #3 może zostać (i na pewno zostanie) zoptymalizowane do wykonania w rejestrach procesora, co jest szybsze. Operacje takie jak przesuwanie bitowe jest realizowane pojedyńczym rozkazem CPU i najczęściej w jednym cyklu zegarowym (pobranie z pamięci poprzez indeks wymaga dużo więcej czasu). Poza tym użycie tablicy char-ów może spowodować dalszą degradację wydajności ze względu na fakt, że
Komentarze (14)
najlepsze
int bit = 0;
while ( val ){
bit+=(val&1)?1:0;
val>>=1;
}
return bit;
int bit=0;
do {bit+=val&1;}
while(val>>=1);
return bit;
Chociaż muszę przyznać, że zmapowanie całego bajtu też jest spoko.
Polecam:
https://graphics.stanford.edu/~seander/bithacks.html
https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
i dalsze.
https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming
znajdziesz wiecej magii. Dodatkowo jeszcze ( a w zasadzie wpierw ):
https://en.wikipedia.org/wiki/Introduction_to_Algorithms
i od strony algorytmicznej każda rekrutacja bedzie formalnoscia.
dziekuje, zakop
@slx2000: Zamierzam zaktualizować wpis, w najbliższym czasie. Dziękuje za poświęcony czas.
Jeśli masz inne uwago to będę wdzięczy.