PDP-8: count number of set bits in a word

[Vincent Slyngstad]

From: Kyle Owen via cctalk: Friday, April 05, 2019 8:59 AM
> Just wondering if anyone has come up with a fast way to count the number of
> 1s in a word on a PDP-8. The obvious way is looping 12 times, rotating the
> word through the link or sign bit, incrementing a count based on the value
> of the link or sign.

That's probably the shortest, but not the fastest.  (I get 13 words.)

You could use RTL and check two bits at a time, for a probably-faster
version.  (That one is 32 words with the loop unrolled.)

> With a small lookup table, you can reduce the total number of loops by
> counting multiple groups of bits at a time, but this of course comes with
> the cost of using more memory. Any other suggestions?

I know a hack to clear a single bit at a time. Here's my first attempt (14 
words):

/
/ Return the number of bits that were set in AC.
CBITS,	.-.
	DCA CBMASK	/ Save the value
	DCA CBCNT	/ No bits yet
CBLP,	TAD CBMASK	/ Get bits, or bits-1
	AND CBMASK	/ Likely clear bottom bit
	SNA 		/ Last one?
	JMP CBRET
	ISZ CBCNT 	/ One more bit
	DCA CBMASK	/ New mask
	CMA		/ Complement bottom bit
	JMP CBLP  	/ ...and go again
CBRET,	TAD CBCNT	/ Get result
	JMP I CBITS	/ ...and return
CBMASK,	.-.
CBCNT,	.-.
$

The run time is related to the number of bits set, and independent of their
position.

It feels like we did this a year or two ago?  Or maybe in the PiDP group?

    Vince