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 <[email protected]> on behalf of Vincent Slyngstad via cctalk <[email protected]> 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
