5 Apr
2019
5 Apr
'19
12:08 p.m.
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