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

[Randy Dawson]

Hi Kyle,

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.

Randy

________________________________
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
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