Bit-sliced indexes: filter and sum fixed-width sensor readings

A bit-sliced index transposes a fixed-width unsigned numeric column into one bitmap per bit position. Bit j is set at row r when the value in row r has bit j set. A less-than query scans slices from most significant to least significant, retaining rows still equal to the threshold prefix and adding rows whose first differing bit is lower. Two such masks make a closed-range filter. A sum over selected rows counts set bits in each slice and weights them by that slice's numeric bit value. The model also supports replacing one existing row by setting or clearing its bit in every slice. Its row domain and bit width are fixed at construction. It retains the source values for audit and does not expose insertion, deletion, null semantics, signed encoding, or compressed bitmaps.

Operational case

Readings 47, 19, 83, 29, 61, and 47 occupy six row positions. The closed range from 29 through 61 selects rows 0, 3, 4, and 5 and sums to 184. Replacing the 83 at row 2 with 37 adds that row to the same filter and raises the sum to 221. The range uses both endpoints; its mask is a set of row IDs rather than a sorted list of values. A query below zero returns no rows, while a threshold beyond the unsigned width includes every row. Editing row 2 must change every affected slice; updating only one bitmap would make a range predicate disagree with the stored value.

Working Python program

class ReadingBitSlices:
    def __init__(self, readings, width=8):
        if width < 1 or any(not isinstance(reading, int) or not 0 <= reading < 1 << width
                            for reading in readings):
            raise ValueError("readings must fit the unsigned fixed-width domain")
        self.readings = list(readings)
        self.width = width
        self.slices = [0] * width
        for row, reading in enumerate(readings):
            for bit in range(width):
                if reading & (1 << bit):
                    self.slices[bit] |= 1 << row

    @property
    def all_rows(self):
        return (1 << len(self.readings)) - 1

    def replace(self, row, reading):
        if not 0 <= reading < 1 << self.width:
            raise ValueError("reading does not fit the column width")
        if not 0 <= row < len(self.readings):
            raise IndexError("row outside column")
        flag = 1 << row
        for bit in range(self.width):
            if reading & (1 << bit):
                self.slices[bit] |= flag
            else:
                self.slices[bit] &= ~flag
        self.readings[row] = reading

    def less_than(self, threshold):
        if threshold <= 0:
            return 0
        if threshold >= 1 << self.width:
            return self.all_rows
        equal, lower = self.all_rows, 0
        for bit in range(self.width - 1, -1, -1):
            ones = self.slices[bit]
            if threshold & (1 << bit):
                lower |= equal & ~ones
                equal &= ones
            else:
                equal &= ~ones
        return lower & self.all_rows

    def between(self, lower, upper):
        return self.less_than(upper + 1) & ~self.less_than(lower) & self.all_rows

    def sum_selected(self, row_mask):
        if row_mask & ~self.all_rows:
            raise ValueError("mask contains an unknown row")
        return sum((self.slices[bit] & row_mask).bit_count() << bit
                   for bit in range(self.width))


if __name__ == "__main__":
    index = ReadingBitSlices([47, 19, 83, 29, 61, 47])
    selected = index.between(29, 61)
    print([row for row in range(6) if selected & (1 << row)], index.sum_selected(selected))
    index.replace(2, 37)
    selected = index.between(29, 61)
    print([row for row in range(6) if selected & (1 << row)], index.sum_selected(selected))

Output

[0, 3, 4, 5] 184
[0, 2, 3, 4, 5] 221

Time, space, and tradeoff

For B value bits and N rows, the logical bitmap payload is B times N bits, plus the retained N values and Python big-integer overhead. Construction and a point replacement touch B bit positions. A less-than predicate uses O(B) big-integer bitmap operations; its machine cost also depends on N divided by the word size, so it is not truly constant per slice. A closed range performs two comparisons and bitwise combination. A selected sum performs B intersections and bit counts. Dense row masks can be effective for repeated analytic predicates, but sparse posting lists may store a low-cardinality selection more economically. An ordinary rank/select bitvector answers positions in one bitmap; this index represents the bits of numeric values across many row bitmaps.

Common Mistakes

Do not read a row mask as a value-ordered result list.
Do not drop the upper endpoint from a closed-range predicate.
Do not leave stale bit slices after a point replacement.
Do not describe Python big-integer bitmap work as O(1) independent of row count.

Connected lessons

Compare this operation boundary with Adaptive radix trees: grow byte-edge nodes as incident codes branch, SimHash bands: find near-duplicate incident fingerprints, Minimal acyclic dictionaries: merge equivalent word suffix states, then complete the audit project and decision quiz.