Revision as of 16:10, 12 August 2019

The population count (or popcount) of a specific value is the number of set bits in that value. For example, the population count of 0F0F₁₆, 1111₁₆, and 00₁₆ are 8₁₀, 4₁₀, and 0₁₀ respectively.

Calculating the population count efficiently has been widely studied with implementations existing for both software and hardware. Many of the popular microprocessors also provide hardware support for this operation.

Implementations

The most basic implementation of a population count function as described in K&R can be written as

int popcount(unsigned x)
{
    int c;
    for (c = 0; x != 0; x >>= 1)
        if (x & 1)
            c++;
    return c;
}

If a large amount of memory is allowed to be used, one can precompile a large lookup table of population count and simply lookup the value from there every time. For example

static uint8_t popcount_tbl[65536] =
{
  /* population count of all the integers 0 through 65535 */
};
int popcount (uint16_t num)
{
    return popcount_tbl[num];
}

Where larger integers can be constructed by breaking them apart, for example with a 32-bit integer one can use popcount() on both the upper and lower 16-bits.

static int popcount32(uint32_t num)
{
    return popcount(num & 0xFFFF) + popcount(num >> 16);
}

Software support

Many programming languages provide a mechanism to perform population count either by implementing it in the language itself or by using intrinsic functions. Below is a short summary of some of them:

Hardware support

Various microprocessors have built-in support for count set bits.

External links

• Counting bits set, in parallel