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_{16}, 1111_{16}, and 00_{16} are 8_{10}, 4_{10}, and 0_{10} 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[edit]

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[edit]

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:

Language | Compiler | Function |
---|---|---|

C | Visual Studio | __popcnt16() __popcnt() __popcnt64() |

GCC | __builtin_popcount() __builtin_popcountl() __builtin_popcountll() | |

Java | - | java.lang.Integer.bitCount() java.lang.Long.bitCount() java.math.BigInteger.bitCount() java.util.BitSet.cardinality() |

C++ | - | std::bitset::count() |

MySQL | - | BIT_COUNT() |

PHP | - | gmp_popcount() |

## Hardware support[edit]

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

ISA | Extension | Mnemonic |
---|---|---|

X86 | SSE4 | POPCNT |

ARM | NEON | VCNT |

System/Z | - | POPCNT |