ECMAScript Proposal. J. S. Choi, 2021. Stage 0.
Bitwise population count (aka “popcount”, “popcnt”, and “bit count”) is a numeric operation that counts the number of 1-bits in an integer’s binary representation. This is a useful and versatile operation in numerics, scientific applications, binary parsing, and many other context—such that it is included as a built-in instruction in many today CPUs; it’s also an instruction in WebAssembly. It is also present in many programming languages’ standard libraries.
Some known use cases are detailed in an article by Vaibhav Sagar. These include:
- Succinct data structures such as Roaring Bitmaps and other rank–select bitmaps for suffix trees, binary trees, and multisets.
- Hash-array-mapped tries (HAMTs).
- Error-correcting codes for strings using their Hamming distance.
- Molecular fingerprinting in chemistry applications.
- Calculating piece mobility of bitboards in chess programming.
- Graph analysis when represented by bitmaps, e.g., calculating adjacency matrices.
Popcount is so pervasive in programs that both GCC and Clang will try to detect popcount implementations and replace them with the built-in CPU instruction. See also LLVM’s detection algorithm. (Note that SIMD-using approaches may often be faster than using dedicated CPU instructions; LLVM/Clang has adopted the former for this reason.)
Popcount is annoying and inefficient to write in JavaScript. We therefore propose exploring the addition of a popcount API to the JavaScript language.
If this proposal is approved for Stage 1, then we would explore various directions for the API’s design. We would also assemble as many real-world use cases as possible and shape our design to fulfill them.
We would probably add a static function to the Math constructor that would look like one the following:
| Precedent | Form | Size | Signed? | Negative-int behavior |
|---|---|---|---|---|
| Python | i.bit_count() |
Bignum | Signed | Input treated as absolute value |
| Wolfram | DigitCount[i, 2, 1] |
Bignum | Signed | Input treated as absolute value |
| Common Lisp | (logcount i) |
Bignum† | Signed | Two’s complement; counts zeroes† |
| Scheme (R7RS)* | (bit-count i) |
Bignum† | Signed | Two’s complement; counts zeroes† |
| Scheme (R6RS) | (bitwise-bit-count i) |
Bignum† | Signed | Two’s complement; counts zeroes then NOTs† |
| GMP | mp_bitcnt_t(i) |
Bignum‡ | Signed | Special behavior‡ |
| C++ | std::popcnt(i) |
8/16/32/64-bit | Unsigned | Forbidden by static typing |
| Go | bits.OnesCount(i), bits.OnesCount8(i), … |
8/16/32/64-bit | Unsigned | Forbidden by static typing |
| Java | Integer.bitCount(i), Long.bitCount(i), … |
16/32-bit; bignum | Signed | Two’s complement (type dependent) |
| Haskell | popCount i |
8/16/≥29/32/64-bit; bignum | Signed | Two’s complement (type dependent) |
| Rust | i.count_ones() |
8/16/32/64/128-bit | Signed | Two’s complement (type dependent) |
| WebAssembly | i32.popcnt, i64.popcnt |
32/64-bit | Signed | Two’s complement (type dependent) |
| MySQL | BIT_COUNT(i) |
64-bit | Signed | Two’s complement (64-bit) |
| Swift | i.nonzeroBitCount§ |
32/64-bit¶ | Signed | Two’s complement¶ |
Table footnotes
* Scheme (R7RS) here refers to SRFI 151, which is implemented in several R7RS implementations, such as in Chicken Scheme.
† When R7RS’s bit-count or Common Lisp’s logcount receives a
negative integer, it returns its number of zeroes instead. For example, both
(bit-count 255) and (bit-count -256) are 8, and both (logcount 256) and
(logcount -257) are 1.
R6RS’s bitwise-bit-count additionally applies bitwise NOT (i.e., one’s
complement – i.e., two’s complement minus one) to the number of zeroes. For
example, (bitwise-bit-count -256) is -9, and (bitwise-bit-count -257) is -2.
‡ GMP’s documentation about mp_bitcnt_t says, “If [the argument is
negative], the number of 1s is infinite, and the return value is the largest
possible mp_bitcnt_t.”
§ Swift’s nonzeroBitCount property forms a trio with its
leadingZeroBitCount and trailingZeroBitCount properties.
¶ Whether Swift’s int type is either 32- or 64-bit depends on its compiler.
We could restrict the function to safe integers; it is uncertain how it should behave on non-safe integers, negative integers, or non-integer numbers.
It is also uncertain whether we should limit it to 32- and/or 64-bit integers
and, if not, whether we should split it up by size (e.g., Math.popcnt(i)
versus Math.popcnt32(i) and Math.popcnt64(i)). A related cross-cutting
concern is how its API would fit with the BigInt Math proposal.
(Lastly, an alternative to adding a popcount function that acts on integers would be to add a bit-array data type with a popcount method. This would probably be considerably more complicated.)