count of bits set in a long

[Theodore A. Camus]

>       unsigned long mask,y;
>
>	y = (mask >> 1) &033333333333;
>	y = mask - y - ((y >>1) & 033333333333);
>	return (((y + (y >> 3)) & 030707070707) % 077);


As chris at mimsy.umd.edu noted, '%' is usually a costly operation.
However, 077 in octal is 63 in decimal, and I believe the following
relationship is true : x % 63 = [(x % 64) + (x / 64)] % 63 and can 
be efficiently calculated by : 

        while (x > 63) {             /* 2 assembly instructions */
          x =  (x & 63)+(x >> 6);    /* 3 assembly instructions */
        }
        if (x = 63)                  /* 1 assembly instruction  */
          return 0                   /* 1 assembly instruction  */
        else                         /* fall through, take value of x */
          return x;                  /*    =  0 instructions         */
         
The loop is not expected to execute approx. log  x times, i.e. not many.
                                                63
Furthermore, although the lookup table method is conceptually elegant,
it has essentially NO locality of reference, and could easily cause several
cache misses, forcing a line fill just to access one byte, whereas this
code-only method will benefit from code pre-fetching etc.


my $2.0e-2  -  Ted



  CSnet:     tac at cs.brown.edu                          Ted Camus  
  ARPAnet:   tac%cs.brown.edu at relay.cs.net             Box 1910 CS Dept
  BITnet:    tac at browncs.BITNET                        Brown University
  "An ounce of example is worth a pound of theory."    Providence, RI 02912