3 ms·

The number of gates required for popcount scales linearly with the input size. It's much, much smaller than a multiplier.

• ryacko 7y ago
  No, it would scale logarithmically if you want to minimize latency.
  • atq2119 7y ago
    It cannot scale logarithmically because you need at least a linear number of gates to represent the inputs. It doesn't have to scale superlinearly either, because the natural circuit using a linear number of adders is already of a logarithmic depth, which is best possible asymptotically.
    • ncmncm 7y ago
      The gate depth scales logarithmically, and that determines how many cycles it takes, or (worse) how fast your cycles can be, if you want the answer in one cycle.
    • ryacko 7y ago
      A lot of complexity could be eschewed if processors weren't faster than 100 Mhz.