[HN Gopher] Pop Goes the Population Count?
       ___________________________________________________________________
        
       Pop Goes the Population Count?
        
       Author : hasheddan
       Score  : 44 points
       Date   : 2025-12-11 14:30 UTC (8 hours ago)
        
 (HTM) web link (xania.org)
 (TXT) w3m dump (xania.org)
        
       | bombcar wrote:
       | Isn't this the instruction that apparently the NSA asked for?
        
         | adgjlsfhk1 wrote:
         | yeah. They understood how useful computing on bits can be
         | before anyone else.
        
         | pklausler wrote:
         | It goes back to the CDC 6600 at least, and is most often seen
         | as part of Hamming distance computation (pop(xor(x,y))). But it
         | turns out to be really useful for other things (trailing zero
         | count), and worth having in hardware since the software
         | sequence is a ~dozen instructions for 64 bits.
        
         | kens wrote:
         | I did a lot of research on this [1]. I got confirmation from
         | Robert Garner (architect of the SPARC processor) that the NSA
         | did indeed ask for the population count instruction. His story
         | of meeting with the NSA is pretty amusing [2].
         | 
         | [1] https://retrocomputing.stackexchange.com/a/8666/4158
         | 
         | [2]
         | https://archive.computerhistory.org/resources/access/text/20...
        
       | majke wrote:
       | Hey! Popcount used to be my favorite instruction. Now I think I
       | prefer LOP3 though :)
        
       | wat10000 wrote:
       | There's a fun approach where do the computation as a tree in
       | parallel. You do a little masking and shifting to add all the
       | even-numbered bits to all the odd-numbered bits, and come up with
       | a set of (assuming we're working on a 64-bit value) 32 partial
       | sums of 2 bits each. Then you add pairs of those to get 16
       | partial sums of 4 bits each, and so forth until you get to the
       | top. This requires six sums, plus shifts and masks for each one.
       | 
       | I don't know if compilers are able to detect this and compile it
       | down to a single instruction, though.
        
         | mattgodbolt wrote:
         | All that and more:
         | https://graphics.stanford.edu/~seander/bithacks.html#CountBi...
         | :)
        
       | taeric wrote:
       | Somewhat related, "Gosper's hack" is a fun way to loop through
       | all of the values that have the same number of 1s.
        
       | dhosek wrote:
       | I still find it wild that Godbolt is his actual name and not some
       | cool term used for the tool to see what compiler output looks
       | like.
        
         | silisili wrote:
         | Same! I always assumed it was the name of the tool until I
         | found out it was a person not long ago.
         | 
         | Maybe a bit of a stretch, but I could see it fitting -
         | https://en.wikipedia.org/wiki/Aptronym
        
       | burnt-resistor wrote:
       | I <3 [AT]BM and BMI[12], and functional-equivalency matching with
       | cost minimization optimization compiler passes.
       | 
       | I wish GCC and LLVM had compiler passes to semi/automagically
       | "vectorize" hot sections using SIMD, i.e., magic transformation
       | of UTF-8 conversion, regex matching, and string functions.
        
       ___________________________________________________________________
       (page generated 2025-12-11 23:01 UTC)