Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!brunix!tac
From: tac@cs.brown.edu (Theodore A. Camus)
Newsgroups: comp.lang.c
Subject: Re: count of bits set in a long
Message-ID: <51467@brunix.UUCP>
Date: 28 Sep 90 15:45:42 GMT
References: <37545@ut-emx.uucp> <3820@goanna.cs.rmit.oz.au> <34281@cup.portal.com> <2859@litchi.bbn.com>
Sender: news@brunix.UUCP
Reply-To: tac@cs.brown.edu (Theodore A. Camus)
Organization: Brown University Department of Computer Science
Lines: 36

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


As chris@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@cs.brown.edu                          Ted Camus  
  ARPAnet:   tac%cs.brown.edu@relay.cs.net             Box 1910 CS Dept
  BITnet:    tac@browncs.BITNET                        Brown University
  "An ounce of example is worth a pound of theory."    Providence, RI 02912