Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!nstn.ns.ca!news.cs.indiana.edu!samsung!usc!zaphod.mps.ohio-state.edu!wuarchive!uunet!fernwood!shograf!jimb
From: jimb@shograf.com (Jim battle)
Newsgroups: comp.arch
Subject: Re: new instructions
Message-ID: <1991May23.204624.22872@shograf.com>
Date: 23 May 91 20:46:24 GMT
References: <24216@lanl.gov> <1991May23.192557.7558@kithrup.COM> <24263@lanl.gov> <1991May23.220143.8515@kithrup.COM>
Reply-To: jimb@shograf.UUCP (Jim battle)
Organization: SHOgraphics
Lines: 32

One place I worked used to ask job applicants to write a program to count
the number of 1's in an integer.  Everyone pretty much did the same thing;
see if the number is odd, tally, and shift.  One person came up with an
ingenious method that does not involve tables or conditionals.  Here is his
solution, given in pseudo assembly language; it assumes 32-bit integers,
although it would work for any word size with little modification:

   Given: r1 is a 32-bit integer with an unknown number of 1's set.

   move #n,r1               /* consider r1 to have 32 1-bit sums */
   move r1,r2               /* destinations are on the right */
   shr  #1,r2
   and  #55555555,r1
   and  #55555555,r2
   add  r2,r1               /* now r1 has 16 two-bit sums; b0+b1, b2+b3, etc */
   move r1,r2
   shr  #2,r2
   and  #33333333,r1
   and  #33333333,r2
   add  r2,r1               /* now r1 has 8 four-bit sums; b0+b1+b2+b3, etc */
   ...
   move r1,r2
   shr  #16,r2
   and  #0000ffff,r1
   and  #0000ffff,r2
   add  r2,r1               /* now r1 has the total of all 1 bits */

for a 64-bit number, just one more step is needed.
maybe not useful, but I thought I'd mention it.

As far as I know, this is an original approach; credit goes to Richard Poppen.
I believe he works at Etak.