pocet jednotiek v slove - algoritmus

[Radek Benedikt]

Dne neděle 19 září 2010 20:20 Jan Waclawek napsal(a):
> Inak toto je typicka uloha ktora sa riesi pomerne trivialne sekvencnou
> logikou (posuvny register a pocitadlo) a uplne netrivialne kombinacnou.
Nevim jak kombinacni logikou, ale zaujalo me to a nasel jsem docela slusny 
rozbor teto ulohy 
http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/ a 
nektere algoritmy jsou opravdu silene.

5) Nifty Parallel Count
#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
#define MASK_00001111 (((unsigned int)(-1))/17)
 int bitcount (unsigned int n) {
   n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
   n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
   n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
   return n % 255 ;
}

tenhle jeste jde ale nasleduji (neni nad The Art of Computer Programming od 
Knuth-a)

6) MIT HAKMEM Count
int bitcount(unsigned int n) {
   /* works for 32-bit numbers only    */
   /* fix last line for 64-bit numbers */

   register unsigned int tmp;

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

Radek