Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Bitvector rank and select: count and locate set bits

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A bitvector stores Boolean flags as bits. Rank1(stop) counts set bits in the half-open prefix [0, stop); select1(ordinal) returns the position of the zero-based ordinal set bit. This index packs flags into 64-bit logical words and stores the number of ones before each word. Rank combines one prefix entry with a masked population count. Select first finds a word whose prefix bracket contains the ordinal, then removes earlier set bits within that word. The bitmap is immutable after construction. Changing a bit would also change every later prefix count, so a mutable design needs a different summary structure or a rebuild.

Operational case

A timeline has active incident flags at positions 19, 47, and 61. Rank1(48) returns 2 because the prefix includes positions 19 and 47. Select1(1) returns 47, and rank at the full length returns 3. A count at stop 47 would exclude the flag at 47; the half-open boundary is part of the contract. The bitmap positions are not incident IDs. A separate mapping is required if the application wants to find an incident record after locating its position. This is a plain packed bitmap with prefix counts, not a compressed bitmap format.

Working Python program

python
"""Static rank/select over a packed incident-state bitmap."""

from bisect import bisect_right


class IncidentBitmap:
    WORD_BITS = 64

    def __init__(self, active_flags: list[bool]):
        self.length = len(active_flags)
        self.words = [0] * ((self.length + self.WORD_BITS - 1) // self.WORD_BITS)
        for position, active in enumerate(active_flags):
            if active:
                self.words[position // self.WORD_BITS] |= 1 << (position % self.WORD_BITS)
        self.ones_before_word = [0]
        for word in self.words:
            self.ones_before_word.append(self.ones_before_word[-1] + word.bit_count())

    def rank1(self, stop: int) -> int:
        if not 0 <= stop <= self.length:
            raise IndexError(stop)
        word_number, offset = divmod(stop, self.WORD_BITS)
        count = self.ones_before_word[word_number]
        if offset:
            count += (self.words[word_number] & ((1 << offset) - 1)).bit_count()
        return count

    def select1(self, ordinal: int) -> int:
        if not 0 <= ordinal < self.ones_before_word[-1]:
            raise IndexError(ordinal)
        word_number = bisect_right(self.ones_before_word, ordinal) - 1
        remaining = ordinal - self.ones_before_word[word_number]
        word = self.words[word_number]
        while remaining:
            word &= word - 1
            remaining -= 1
        lowest_bit = word & -word
        return word_number * self.WORD_BITS + lowest_bit.bit_length() - 1


incident_bitmap = IncidentBitmap([False] * 19 + [True] + [False] * 27 + [True] + [False] * 13 + [True])
print(incident_bitmap.rank1(48))
print(incident_bitmap.select1(1))
print(incident_bitmap.rank1(incident_bitmap.length))

Output

Output
2
47
3

Time, space, and tradeoff

Building from N input flags scans O(N) values and allocates O(ceil(N/64)) Python integers for words and the same order of prefix counts. Rank uses O(1) indexed operations plus a population count on a bounded 64-bit word. Select binary-searches the prefix array in O(log(N/64)) comparisons and removes at most 63 bits, so the within-word phase is bounded by a constant. An empty bitmap has rank zero but no valid select ordinal. Python integers and lists add object overhead beyond the logical bit count, so this example should not be marketed as a measured succinct encoding.

Common Mistakes

  • Do not treat rank's stop position as inclusive.
  • Do not use one-based select ordinals against this zero-based API.
  • Do not mutate packed words without repairing later prefix counts.
  • Do not claim this Python representation uses exactly N bits of memory.

Connected lessons

Test this invariant in the incident flag and path audit, then answer the contract quiz.

Binary tries: choose a maximum-XOR fingerprint adds a related operation contract.

Segmented arrays: locate blocks through cumulative lengths adds a related sequence operation contract.

Elias–Fano: split sorted IDs into low parts and high bits adds a compact lookup contract.

Chunked integer sets: switch sparse arrays to dense bitmaps adds a compact lookup contract.

Wavelet matrices: count frequencies and find subarray quantiles adds a distinct structure contract to compare.

Bit-sliced indexes: filter and sum fixed-width sensor readings examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details