<p>An excellent recent study comparing several of the most modern techniques for counting the <strong><em>number of 'set' (1-valued) bits</em></strong> in a range of memory (<em>aka</em> <a href="https://en.wikipedia.org/wiki/Hamming_weight" rel="nofollow noreferrer">Hamming Weight</a>, <em>bitset cardinality</em>, <em>sideways sum</em>, <em>population count</em> or <a href="https://software.intel.com/en-us/node/679649" rel="nofollow noreferrer"><code>popcnt</code></a>, <em>etc.</em>) can be found in Wojciech, Kurz, and Lemire (2017), <a href="https://arxiv.org/pdf/1611.07612.pdf" rel="nofollow noreferrer"><em>Faster population counts using AVX2 instructions</em></a><sup> <a href="https://i.stack.imgur.com/69xAm.png" rel="nofollow noreferrer">1</a></sup></p>

<p>The following is a complete, tested, and fully-working <strong>C#</strong> adaptation of the "Harley-Seal" algorithm from that paper, which the authors found to be the fastest method that uses general-purpose bitwise operations (that is, that doesn't require special hardware).</p>

<p><strong>1. Managed array entry points</strong><br>(optional) Provides access to the block-optimized bit-counting for managed array <code>ulong[]</code>.</p>

<pre><code>/// &lt;summary&gt; Returns the total number of 1-valued bits in the array &lt;/summary&gt;
[DebuggerStepThrough]
public static int OnesCount(ulong[] rg) =&gt; OnesCount(rg, 0, rg.Length);

/// &lt;summary&gt; Finds the total number of '1' bits in an array or its subset &lt;/summary&gt;
/// &lt;param name="rg"&gt; Array of ulong values to scan &lt;/param&gt;
/// &lt;param name="index"&gt; Starting index in the array &lt;/param&gt;
/// &lt;param name="count"&gt; Number of ulong values to examine, starting at 'i' &lt;/param&gt;
public static int OnesCount(ulong[] rg, int index, int count)
{
    if ((index | count) &lt; 0 || index &gt; rg.Length - count)
        throw new ArgumentException();

    fixed (ulong* p = &amp;rg[index])
        return OnesCount(p, count);
}
</code></pre>

<p><strong>2. Scalar API</strong><br>Used by the block-optimized counter to aggregate results from the carry-save adder, and also to finish up any remainder for block sizes not divisible by the optimized chunk size of 16 x 8 bytes/ulong = 128 bytes. Suitable for general-purpose use also.</p>

<pre><code>/// &lt;summary&gt; Finds the Hamming Weight or ones-count of a ulong value &lt;/summary&gt;
/// &lt;returns&gt; The number of 1-bits that are set in 'x' &lt;/returns&gt;
public static int OnesCount(ulong x)
{
    x -= (x &gt;&gt; 1) &amp; 0x5555555555555555;
    x = ((x &gt;&gt; 2) &amp; 0x3333333333333333) + (x &amp; 0x3333333333333333);
    return (int)((((x + (x &gt;&gt; 4)) &amp; 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) &gt;&gt; 56);
}
</code></pre>

<p><strong>3. <em>"Harley-Seal"</em> block-optimized 1s-bit counter</strong><br>Processes blocks of 128 bytes at a time, i.e., 16 <code>ulong</code> values per block. Uses the carry-save adder (shown below) to gang-add single bits across adjacent <code>ulong</code>s, and aggregates totals upwards as powers of two.</p>

<pre><code>/// &lt;summary&gt; Count the number of 'set' (1-valued) bits in a range of memory. &lt;/summary&gt;
/// &lt;param name="p"&gt; Pointer to an array of 64-bit ulong values to scan &lt;/param&gt;
/// &lt;param name="c"&gt; Size of the memory block as a count of 64-bit ulongs &lt;/param&gt;
/// &lt;returns&gt; The total number of 1-bits &lt;/returns&gt;
public static int OnesCount(ulong* p, int c)
{
    ulong z, y, x, w;
    int c = 0;

    for (w = x = y = z = 0UL; cq &gt;= 16; cq -= 16)
        c += OnesCount(CSA(ref w,
                            CSA(ref x,
                                CSA(ref y,
                                    CSA(ref z, *p++, *p++),
                                    CSA(ref z, *p++, *p++)),
                                CSA(ref y,
                                    CSA(ref z, *p++, *p++),
                                    CSA(ref z, *p++, *p++))),
                            CSA(ref x,
                                CSA(ref y,
                                    CSA(ref z, *p++, *p++),
                                    CSA(ref z, *p++, *p++)),
                                CSA(ref y,
                                    CSA(ref z, *p++, *p++),
                                    CSA(ref z, *p++, *p++)))));

    c &lt;&lt;= 4;
    c += (OnesCount(w) &lt;&lt; 3) + (OnesCount(x) &lt;&lt; 2) + (OnesCount(y) &lt;&lt; 1) + OnesCount(z);

    while (--cq &gt;= 0)
        c += OnesCount(*p++);

    return c;
}
</code></pre>

<p><strong>4. Carry-save adder (CSA)</strong></p>

<pre><code>/// &lt;summary&gt; carry-save adder &lt;/summary&gt;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong CSA(ref ulong a, ulong b, ulong c)
{
    ulong v = a &amp; b | (a ^ b) &amp; c;
    a ^= b ^ c;
    return v;
}
</code></pre>

<p><hr>
<strong>Remarks</strong></p>

<p>Because the approach shown here counts the total number of 1-bits by proceeding 128-byte chunks at a time, it only becomes optimal with larger memory block sizes. For example, likely at least some (small) multiple of that sixteen-qword (16-<code>ulong</code>) chunk size. For counting 1-bits in smaller memory ranges, this code will work correctly, but drastically underperform more naïve methods. See the paper for details.</p>

<p>From the paper, this diagram summarizes how the <a href="https://en.wikipedia.org/wiki/Carry-save_adder" rel="nofollow noreferrer">Carry-Save Adder</a> works:</p>

<p><a href="https://i.stack.imgur.com/69xAm.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/69xAm.png" alt="Carry-Save Adder in &#39;Harley-Seal&#39; block-optimized bit count"></a>
<br><br><hr>
<strong>References</strong></p>

<p>[1.]  Muła, Wojciech, Nathan Kurz, and Daniel Lemire. "Faster population counts using AVX2 instructions." The Computer Journal 61, no. 1 (2017): 111-120.</p>
Bit counting in a contiguous memory chunk
<p>I was asked in an interview the following question.</p>

<pre><code>int countSetBits(void *ptr, int start, int end); 
</code></pre>

<p><strong>Synopsis:</strong> 
Assume that <code>ptr</code> points to a big chunk of memory. Viewing this memory as contiguous sequence of bits, <code>start</code> and <code>end</code> are bit positions. Assume <code>start</code> and <code>end</code> 
have proper values and <code>ptr</code> is pointing to an initialized chunck of memory. </p>

<p><strong>Question:</strong> 
Write a C code to count number of bits set from <code>start</code> to <code>end</code> [inclusive] and return the count. </p>

<p>Just to make it more clear </p>

<pre><code> ptr----&gt;+-------------------------------+
         | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
         +-------------------------------+
         | 8 | 9 |                   |15 |
         +-------------------------------+
         |                               |
         +-------------------------------+
              ...
              ...
         +-------------------------------+
         |               | S |           |
         +-------------------------------+
              ...
              ...
         +-------------------------------+
         |    | E |                      |
         +-------------------------------+
              ...
              ...
</code></pre>

<p>My solution: </p>

<pre><code>int countSetBits(void *ptr, int start, int end )
{
    int count = 0, idx; 

    char *ch; 

    for (idx = start; idx &lt;= end; idx++) 
    {     ch = ptr + (idx/8); 

          if((128 &gt;&gt; (idx%8)) &amp; (*ch)) 
          {
                   count++; 
          }
    }

    return count; 
}
</code></pre>

<p>I gave a very lengthy and somewhat inefficient code during the interview. I worked on it later and came up with above solution. </p>

<p>I am very sure SO community can provide more elegant solution. I am just curious to see their response. </p>

<p>PS: Above code is not compiled. It is more like a pseudo code and may contain errors. </p>