Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!samsung!uakari.primate.wisc.edu!sdd.hp.com!think.com!yale!cs.yale.edu!!rabin
From: rabin@CS.Yale.Edu (Dan Rabin)
Newsgroups: comp.arch
Subject: Re: new instructions
Message-ID: <RABIN.91May24143845@epic.CS.Yale.Edu>
Date: 24 May 91 14:38:45 GMT
References: <24216@lanl.gov> <1991May23.192557.7558@kithrup.COM>
	<24263@lanl.gov> <1991May23.220143.8515@kithrup.COM>
	<1991May23.204624.22872@shograf.com>
Sender: news@cs.yale.edu (Usenet News)
Reply-To: rabin-dan@cs.yale.edu
Organization: Computer Science, Yale University, New Haven, CT 06520-2158
Lines: 39
In-Reply-To: jimb@shograf.com's message of 23 May 91 20: 46:24 GMT
Nntp-Posting-Host: epic.systemsz.cs.yale.edu

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