PDP-8: count number of set bits in a word
rdawson16 at hotmail.com
Fri Apr 5 15:49:16 CDT 2019
hat's a really interesting problem, and the government (NSA) wanted this badly and done FAST.
they asked Seymour Cray to create a specific instruction for this and they called it 'population count'
Anybody know the why and how it is useful?
I am deep in matrix math books and 'classification algorithms' in statistics math, looking into electronics reliability WCCA, so this is an interesting topic.
From: cctalk <cctalk-bounces at classiccmp.org> on behalf of Vincent Slyngstad via cctalk <cctalk at classiccmp.org>
Sent: Friday, April 5, 2019 12:08 PM
To: Kyle Owen; General Discussion: On-Topic and Off-Topic Posts
Subject: Re: PDP-8: count number of set bits in a word
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
/ Return the number of bits that were set in AC.
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?
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
The run time is related to the number of bits set, and independent of their
It feels like we did this a year or two ago? Or maybe in the PiDP group?
More information about the cctalk