🚀 go-pugleaf

In article <1991May23.204624.22872@shograf.com> jimb@shograf.com (Jim
battle) gives a technique (credited to Richard Poppen) for counting
the number of one-bits in a word.

For historical interest, a similar technique was proposed in 

    HAKMEM  -  Artificial Intelligence Memo No. 239
    Massachusetts Institute of Technology A. I. Laboratory
    M. Beeler, R. W. Gosper & R. Schroeppel, February 29,1972

The relevant excerpt is:

    ITEM 25 (in order of one-ups-manship:  Gosper, Mann, Lenard, [Root and
    Mann]):

    To count the ones in a PDP-6/10 word:

	    LDB B,[014300,,A]       ;or MOVE B,A then LSH B,-1
	    AND B,[333333,,333333]
	    SUB A,B
	    LSH B,-1
	    AND B,[333333,,333333]
	    SUBB A,B   ;each octal digit is replaced by number of 1's in it
	    LSH B,-3
	    ADD A,B
	    AND A,[070707,070707]
	    IDIVI A,77              ;casting out 63.'s

    These ten instructions, with constants extended, would  work  on  word
    lengths up to 62.;  eleven suffice up to 254..

This proposal uses an integer divide instruction to carry out the
summation; the remainder is the result of interest.  This is
ingenious, but possibly disadvantageous on a RISC that lacks a divide
instruction.  The same result could be obtained by a short sequence of
shifts and adds, I think.

  -- Dan Rabin
     rabin-dan@cs.yale.edu