<p>See</p>

<p><a href="https://arxiv.org/abs/1911.02696" rel="nofollow noreferrer">Efficient Computation of Positional Population Counts Using SIMD Instructions</a> by Marcus D. R. Klarqvist, Wojciech Muła, Daniel Lemire (7 Nov 2019)</p>

<p><a href="https://arxiv.org/abs/1611.07612" rel="nofollow noreferrer">Faster Population Counts using AVX2 Instructions</a> by Wojciech Muła, Nathan Kurz, Daniel Lemire (23 Nov 2016).</p>

<p>Basically, each full adder compresses 3 inputs to 2 outputs. So one can eliminate an entire 256-bit word for the price of 5 logic instructions. The full adder operation could be repeated until registers become exhausted. Then results in the registers are accumulated (as seen in most of the other answers). </p>

<p>Positional popcnt for 16-bit subwords is implemented here:
<a href="https://github.com/mklarqvist/positional-popcount" rel="nofollow noreferrer">https://github.com/mklarqvist/positional-popcount</a></p>

<pre><code>// Carry-Save Full Adder (3:2 compressor)
b ^= a;
a ^= c;
c ^= b; // xor sum
b |= a;
b ^= c; // carry
</code></pre>

<p><em>Note: the accumulate step for positional-popcnt is more expensive than for normal <a href="https://github.com/kimwalisch/libpopcnt" rel="nofollow noreferrer">simd popcnt</a>. Which I believe makes it feasible to add a couple of half-adders to the end of the CSU, it might pay to go all the way up to 256 words before accumulating.</em></p>
Count each bit-position separately over many 64-bit bitmasks, with AVX but not AVX2
<p>(Related: <a href="https://stackoverflow.com/questions/7793997/how-to-quickly-count-bits-into-separate-bins-in-a-series-of-ints-on-sandy-bridge">How to quickly count bits into separate bins in a series of ints on Sandy Bridge?</a> is an earlier duplicate of this, with some different answers.  Editor's note: the answers here are probably better.</p>

<p>Also, an AVX2 version of a similar problem, with many bins for a whole row of bits much wider than one <code>uint64_t</code>: <a href="https://stackoverflow.com/questions/58486138/improve-column-population-count-algorithm">Improve column population count algorithm</a>)</p>

<hr>

<p>I am working on a project in C where I need to go through tens of millions of masks (of type ulong (64-bit)) and update an array (called <code>target</code>) of 64 short integers (uint16) based on a simple rule:</p>

<pre><code>// for any given mask, do the following loop
for (i = 0; i &lt; 64; i++) {
    if (mask &amp; (1ull &lt;&lt; i)) {
        target[i]++
    }
}
</code></pre>

<p>The problem is that I need do the above loops on tens of millions of masks and I need to finish in less than a second. Wonder if there are any way to speed it up, like using some sort special assembly instruction that represents the above loop.  </p>

<p>Currently I use gcc 4.8.4 on ubuntu 14.04 (i7-2670QM, supporting AVX, not AVX2) to compile and run the following code and took about 2 seconds. Would love to make it run under 200ms.</p>

<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include &lt;sys/time.h&gt;
#include &lt;sys/stat.h&gt;

double getTS() {
    struct timeval tv;
    gettimeofday(&amp;tv, NULL);
    return tv.tv_sec + tv.tv_usec / 1000000.0;
}
unsigned int target[64];

int main(int argc, char *argv[]) {
    int i, j;
    unsigned long x = 123;
    unsigned long m = 1;
    char *p = malloc(8 * 10000000);
    if (!p) {
        printf("failed to allocate\n");
        exit(0);
    }
    memset(p, 0xff, 80000000);
    printf("p=%p\n", p);
    unsigned long *pLong = (unsigned long*)p;
    double start = getTS();
    for (j = 0; j &lt; 10000000; j++) {
        m = 1;
        for (i = 0; i &lt; 64; i++) {
            if ((pLong[j] &amp; m) == m) {
                target[i]++;
            }
            m = (m &lt;&lt; 1);
        }
    }
    printf("took %f secs\n", getTS() - start);
    return 0;
}
</code></pre>

<p>Thanks in advance!</p>