You Won’t Believe This One Weird CPU Instruction!

submited by

Style Pass

2021-06-11 08:30:05

Most CPU architectures in use today have an instruction called popcount, short for “population count”. Here’s what it does: it counts the number of set bits in a machine word. For example (assuming 8-bit words for simplicity), popcount(00100110) is 3 and popcount(01100000) is 2.

You might be wondering, like I was, if there’s more to this instruction, but that’s all it does! This doesn’t seem very useful, right?

I thought this might be a recent addition for some hyperspecialised use case, but it has in fact been present in CPU architectures since at least 1961:

popcount is also known as “The NSA Instruction”, and a very entertaining thread on comp.arch discusses its uses inside and outside cryptography. It is rumoured that it was originally added to CPU instructions at the behest of the NSA. As this archived email thread puts it:

It was almost a tradition that one of the first of any new faster CDC machine was delivered to a “good customer” - picked up at the factory by an anonymous truck, and never heard from again.