PDP-8: count number of set bits in a word
Vincent Slyngstad
v.slyngstad at frontier.com
Fri Apr 5 14:08:53 CDT 2019
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
More information about the cctalk
mailing list