| Latest revision |
Your text |
| Line 1: |
Line 1: |
| − | {{title|Population Count (popcount)}}[[File:Popcount.svg|right]]
| + | The '''population count''' (or '''popcount''') of a specific value is the number of [[set bits]] in that value. For example, the population count of 0x0F0F, 0x1111, and 0x00 are 8, 4, and 0 respectively. |
| − | The '''population count''' (or '''popcount''') of a specific value is the number of [[set bits]] in that value. For example, the population count of {{hex|0F0F}}, {{hex|1111}}, and {{hex|00}} are {{dec|8}}, {{dec|4}}, and {{dec|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. | + | Calculating the population count efficiently has widely studied with both software and hardware implementations provided by many popular [[microprocessors]]. |
| | | | |
| − | == Implementations ==
| |
| − | The most basic implementation of a population count function as described in K&R can be written as
| |
| − |
| |
| − | <source lang="c">
| |
| − | int popcount(unsigned x)
| |
| − | {
| |
| − | int c = 0;
| |
| − | for (; x != 0; x >>= 1)
| |
| − | if (x & 1)
| |
| − | c++;
| |
| − | return c;
| |
| − | }
| |
| − | </source>
| |
| − |
| |
| − | 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
| |
| − |
| |
| − | <source lang="c">
| |
| − | static uint8_t popcount_tbl[65536] =
| |
| − | {
| |
| − | /* population count of all the integers 0 through 65535 */
| |
| − | };
| |
| − | int popcount (uint16_t num)
| |
| − | {
| |
| − | return popcount_tbl[num];
| |
| − | }
| |
| − | </source>
| |
| − |
| |
| − | 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.
| |
| − |
| |
| − | <source lang="c">
| |
| − | static int popcount32(uint32_t num)
| |
| − | {
| |
| − | return popcount(num & 0xFFFF) + popcount(num >> 16);
| |
| − | }
| |
| − | </source>
| |
| − |
| |
| − | A more advanced algorithm that is also quicker, combining subtraction and bitwise AND:
| |
| − |
| |
| − | <source lang="c">
| |
| − | int popcount(unsigned x)
| |
| − | {
| |
| − | int c = 0;
| |
| − | for (; x != 0; x &= x - 1)
| |
| − | c++;
| |
| − | return c;
| |
| − | }
| |
| − | </source>
| |
| − |
| |
| − | == 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:
| |
| − |
| |
| − | {| class="wikitable sortable"
| |
| − | |-
| |
| − | ! Language !! Compiler !! Function
| |
| − | |-
| |
| − | | rowspan="2" | [[C]] || [[Visual Studio]] || __popcnt16()<br />__popcnt()<br />__popcnt64()
| |
| − | |-
| |
| − | | [[GCC]] || __builtin_popcount()<br />__builtin_popcountl()<br />__builtin_popcountll()
| |
| − | |-
| |
| − | | [[C++]] || - || std::bitset::count()<br>std::popcount() since C++20
| |
| − | |-
| |
| − | | [[.NET Core (3.0+)]] || - || System.Numerics.BitOperations.PopCount()
| |
| − | |-
| |
| − | | [[Java]] || - || java.lang.Integer.bitCount()<br />java.lang.Long.bitCount()<br />java.math.BigInteger.bitCount()<br />java.util.BitSet.cardinality()
| |
| − | |-
| |
| − | | [[MySQL]] || - || BIT_COUNT()
| |
| − | |-
| |
| − | | [[PHP]] || - || gmp_popcount()
| |
| − | |-
| |
| − | | [[python|Python (3.10+)]] || - || int.bit_count()
| |
| − | |-
| |
| − | | [[Rust]] || - || count_ones()
| |
| − | |}
| |
| − |
| |
| − | == Hardware support ==
| |
| − | Various [[microprocessors]] have built-in support for count set bits.
| |
| − |
| |
| − | {| class="wikitable sortable"
| |
| − | |-
| |
| − | ! [[ISA]] !! Extension !! [[Mnemonic]] !!
| |
| − | |-
| |
| − | | rowspan="3" | [[X86]] || POPCNT || POPCNT || 16/32/64-bit operands
| |
| − | |-
| |
| − | | {{x86|AVX512_BITALG}} || VPOPCNTB/VPOPCNTW || Parallel population count on 8/16-bit operands in 128/256/512-bit vector
| |
| − | |-
| |
| − | | {{x86|AVX512_VPOPCNTDQ}} || VPOPCNTD/VPOPCNTQ || Parallel population count on 32/64-bit operands in 128/256/512-bit vector
| |
| − | |-
| |
| − | | [[ARM]] || [[NEON]] || VCNT ||
| |
| − | |-
| |
| − | | [[System/Z]] || - || POPCNT ||
| |
| − | |}
| |
| − |
| |
| − | ==External links ==
| |
| − | * [http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel Counting bits set, in parallel]
| |
| | | | |
| | [[Category:Binary arithmetic]] | | [[Category:Binary arithmetic]] |
