Bitset Representation and Word-Level Rank and Select

A bitvector is the cheapest possible encoding of a set over a dense universe: n bits, n/8 bytes, one bit per element. The cost of that encoding is that every operation becomes a scan, so the useful structures are not bitvectors but bitvectors plus a small index that converts prefix queries into a constant number of loads. The index is what makes the word “succinct” mean something specific: the structure stores n bits plus o(n) bits, where o(n) is a quantity that grows more slowly than n itself, so the asymptotic space is still n bits while every query is O(1).

The two queries everything else is built from

rank₁(i) returns the number of set bits in positions 0 through i - 1. select₁(j) returns the position of the j-th set bit, counting from 0. The pair is asymmetric in difficulty: rank is a prefix sum and decomposes into blocks, while select is an inverse permutation and needs a sampled directory plus a local search.

Both are defined on 1-bits here; the 0-bit versions are the same functions on the complement, and a structure that needs both either stores two indexes or stores one plus the total length.

The reason these two operations matter beyond bitvectors is that almost every succinct structure encodes its data as a bitvector with a fixed structural meaning and then answers its real queries in terms of rank and select. A balanced-parentheses tree encoding answers “parent of node i” as a select of the matching parenthesis; a wavelet tree answers a range count as a sequence of rank queries on levels. Get rank and select right and the rest of the cluster is composition.

rank from popcount and a block directory

The direct computation of rank₁(i) is a loop over i/64 words, which is O(n/64) — too slow for a per-query operation, and unnecessary because the prefix counts can be precomputed.

The standard two-level layout uses a superblock of 512 bits, containing eight 64-bit words. For each superblock, store its starting rank as a 32-bit or 64-bit integer. For each word within a superblock, store the number of set bits in the preceding words of that superblock, which is at most 448 and therefore fits in 9 bits. A query then loads one superblock counter, one per-word counter, and one word, and computes the remaining popcount of the partial word — three loads and a popcount, with no loop over the preceding words.

#include <stdint.h>

/* bits[] holds n/64 words. super[] has one entry per 512 bits: the rank at
   the start of that superblock, as a 64-bit value so that n may exceed 2^32.
   sub[] has one 16-bit entry per word: the number of set bits in the preceding
   words of the same superblock (0..448). */
static uint64_t rank1(const uint64_t *bits, const uint64_t *super,
                      const uint16_t *sub, uint64_t i) {
    uint64_t w = i >> 6, b = i & 63;
    uint64_t s = super[w >> 3];
    uint64_t within = sub[w];
    uint64_t partial = bits[w] & ((1ULL << b) - 1);   /* defined for b < 64 */
    return s + within + (uint64_t)__builtin_popcountll(partial);
}

The mask is the one place this goes wrong. (1ULL << b) - 1 is defined for every b in 0..63 and yields zero for b == 0, which is the behaviour wanted. The tempting alternative ~0ULL >> (64 - b) shifts by 64 when b == 0, which is undefined behaviour in C and produces an all-ones mask on some compilers and zero on others.

The nine-bit field packing deserves a note. Eight words per superblock, each needing a count up to 448, needs nine bits per field, and eight fields of nine bits is 72 bits — more than a 64-bit word. The packed encoding therefore does not fit, and implementations either use a 16-bit entry per word (as above) or shrink the superblock to four words and pack four nine-bit fields into 36 bits. The 16-bit entry costs seven bits more per word than a packed nine-bit field would, which is about 0.11 bits per stored bit — a real cost that is usually accepted for the simpler addressing.

The space cost with a 16-bit sub-array is 1 bit per bit for the bitvector, plus 64 bits per 512 bits for superblocks (1/8 bit per bit) plus 16 bits per 64 bits (1/4 bit per bit). Total overhead is 3/8 of the vector’s own size, or roughly 38 percent. A 32-bit superblock counter — usable while n stays below 2³² — cuts the first term to 1/16 and brings the total to about 31 percent. Either way the index is a constant fraction of the payload rather than a sublinear one: the formal n + o(n) bound needs block and counter sizes that grow with log n, so that the number of counters per stored bit shrinks as n grows. The fixed 512-bit layout chooses the other trade — simple addressing and small constants at the cost of a constant-factor space overhead — and it is the layout most implementations use.

popcount on a 64-bit word is cheap on current targets but not uniform. On x86-64 it is the POPCNT instruction, added with the SSE4.2 extensions in the Nehalem generation, and available unconditionally on the machines that run server code today. On AArch64 the same computation expands to the SIMD CNT instruction on a vector register plus a horizontal add, which is a handful of instructions rather than one. On targets with neither, the fallback is a multiply-and-shift sequence over the word using the standard bit-twiddling constants, which is a dozen arithmetic operations rather than 64 iterations.

select needs a sampled directory

Select cannot be decomposed into prefix sums, because the position of the j-th one is not a local function of the bits near it. Two approaches are in use.

Sample every k-th one. Store the position of every 512th set bit in a directory, then from the sampled position scan forward for the remaining j mod 512 ones. The scan is over words: skip words that are zero, and within a non-zero word use a bit trick to find the r-th one. With a sample interval of 512, the scan is bounded by 512 ones, which in the worst case — all bits set — is 8 words. The directory costs 32 bits per 512 ones, which is 1/16 bit per one, but only if the bitvector is dense. On a sparse bitvector the directory is sized by the number of ones, so its cost is per-one rather than per-bit; the bitvector itself is still n bits, and storing the positions of the ones explicitly instead would cost about m log(n/m) bits for m ones.

Interleave rank and select. Store the select directory in the gaps of the rank structure. This is the approach Vigna’s broadword paper analyses, and it lets both queries share one set of counters. The implementation is more intricate and the constant factors are better on dense vectors.

The local search within a word is the interesting part. Given a 64-bit word and a rank r, find the position of the r-th one. The portable method is a loop of popcount on halves — binary search over the word, six steps — which is O(log 64) and branchless if written with conditional moves. The broadword method computes the position with a fixed sequence of arithmetic and comparison operations on the word and a mask, with no branches and no loop; it is the technique the name refers to.

#include <stdint.h>

/* Position of the r-th set bit of x, with 1 <= r <= popcount(x).
   Binary search on population counts: six steps for a 64-bit word. */
static int select_in_word(uint64_t x, unsigned r) {
    int pos = 0;
    unsigned c;
    c = (unsigned)__builtin_popcountll(x & 0x00000000FFFFFFFFULL);
    if (c < r) { pos += 32; x >>= 32; r -= c; }
    c = (unsigned)__builtin_popcountll(x & 0x000000000000FFFFULL);
    if (c < r) { pos += 16; x >>= 16; r -= c; }
    c = (unsigned)__builtin_popcountll(x & 0x00000000000000FFULL);
    if (c < r) { pos += 8;  x >>= 8;  r -= c; }
    c = (unsigned)__builtin_popcountll(x & 0x000000000000000FULL);
    if (c < r) { pos += 4;  x >>= 4;  r -= c; }
    c = (unsigned)__builtin_popcountll(x & 0x0000000000000003ULL);
    if (c < r) { pos += 2;  x >>= 2;  r -= c; }
    c = (unsigned)__builtin_popcountll(x & 0x0000000000000001ULL);
    if (c < r) { pos += 1; }
    return pos;
}

Six steps locate the bit exactly. The branches are predictable in aggregate but mispredict on random data, which is why the branchless broadword formulation exists: it replaces each conditional with a mask computed from a comparison, so the instruction count is constant. The loop version above is the one to write first, because it is obviously correct; the branchless version is an optimization applied after the surrounding structure works.

Space-time trade-offs that actually get chosen

The parameters are the superblock size, the sub-block size, and the select sample interval. Larger superblocks mean fewer counters but a longer local scan; smaller superblocks mean more counters and shorter scans. The commonly used configuration is 512-bit superblocks with 64-bit sub-blocks for rank, which puts the local popcount at one word, and 512-one samples for select, which puts the local scan at eight words worst case.

Pushing further in either direction has a cost that the asymptotics hide:

• Superblock 4096 bits: the superblock counter term falls to 1/64 bit per bit (64 bits per 4096), but the per-word sub-block counters still dominate at 1/4, so the total is about 0.27 bits per bit. The query is unchanged, because the local popcount is still one word.
• Sub-block 512 bits instead of 64: the local popcount becomes eight words, so rank costs up to eight popcounts. One counter per 512 bits instead of eight 16-bit counters saves about 0.22 bits per bit of the index, which does not pay for the extra work.
• Select sample 64: the directory is eight times larger, 1/2 bit per one, and the scan is at most one word.

A structure that must support both rank and select on both 0s and 1s is the case where doubling the index matters, but the cost is a second directory of the same kind rather than anything proportional to the density of the vector, as long as the representation stays a bitvector with counters. Replacing the bitvector with explicit positions of the ones is the point at which the space becomes proportional to the number of ones.

Where this connects to the rest of the cluster

A bitvector with rank and select is the substrate for three other articles here. The Elias-Fano encoding of a monotone sequence stores its low bits in a bitvector and its high bits as a unary gap sequence, and answers “how many values are below x” with two rank queries — see Elias-Fano Encoding for Monotone Integer Sequences. A wavelet tree stores one bitvector per level and answers range counting by descending levels, one rank query per level — see Wavelet Trees and Range Queries on Sequences. A balanced-parentheses tree encoding stores the tree shape as 2n bits and answers navigation with rank, select, and the matching-parenthesis operation, which needs an additional o(n) index — see Balanced Parentheses and Succinct Tree Navigation.

The disjoint-set structures earlier in the cluster use none of this. They are pointer-based, they store Θ(n) words rather than Θ(n) bits, and their queries are O(α(n)) rather than O(1). The two families meet in applications that need both connectivity and order, such as compressed graph representations that keep a component labelling in a bitvector and a spanning structure in a parentheses encoding.