A bitmap index shines on LOW-CARDINALITY columns (a status enum, a boolean flag, a handful of categories) where a B-tree or hash index would be wasteful. One bitmap per distinct value; bit i set means row i has that value. The payoff: combining conditions on DIFFERENT bitmap-indexed columns -- a real WHERE color = 'red' AND size = 'large' -- becomes a plain bitwise AND of two integers. No row-by-row comparison at all.

bitmap_to_rows/bitmap_and/bitmap_or (given) are the low-level bit utilities. Implement:

• BitmapIndex.__init__(self, values): values is a list of column values, one per row (row i's value is values[i]). Build self.bitmaps: a dict mapping each DISTINCT value to a bitmask int, with bit row set for every row whose value equals that key. Also record self._num_rows -- query_not needs to know exactly how many bits are "in play".
• query(self, value): return the list of row indices where the column equals value (self.bitmaps might not even have an entry for a value that never appeared).
• query_in(self, values): return the sorted list of row indices where the column equals ANY of values -- a real WHERE color IN (...). OR the relevant bitmaps together, then convert once.
• query_not(self, value): return the sorted list of row indices where the column does NOT equal value -- a real WHERE color != 'red'.

The missing link: Python integers don't have a fixed width

In C or Java, "flip every bit" for a NOT query is just ~bitmap -- those languages' integers are a fixed width (32, 64 bits), so flipping every bit gives you exactly "every row not set", nothing more. Python integers have NO fixed width: they grow as needed, and ~x is defined as -x - 1 (two's complement), which for a positive bitmap produces a NEGATIVE number with infinitely many set bits above the ones you actually care about. Feed that straight into bitmap_to_rows and its while bitmap: loop never terminates (a negative Python int right-shifts toward -1, never 0) -- your query hangs instead of returning a wrong answer, which is almost worse: it looks like an unrelated deadlock, not an off-by-infinity in your indexing.

The fix: build an explicit mask of exactly self._num_rows set bits -- (1 << self._num_rows) - 1 -- and XOR (or subtract) the excluded bitmap from THAT, never from Python's unbounded ~.

Example

idx = BitmapIndex(["red", "blue", "red", "green", "red"])
idx.query("red")               # -> [0, 2, 4]
idx.query_in(["red", "green"]) # -> [0, 2, 3, 4]
idx.query_not("red")           # -> [1, 3]

# combining across two separate indexed columns:
color_idx = BitmapIndex(["red", "blue", "red"])
size_idx = BitmapIndex(["large", "large", "small"])
bitmap_to_rows(bitmap_and(color_idx.bitmaps["red"], size_idx.bitmaps["large"]))
# -> [0]   ("red AND large" -- only row 0 matches both)

Constraints

• 1 << row is how you set just bit row -- OR-ing that into a value's accumulated bitmap is what builds it up as you scan through values.
• query/query_in on a value that never appeared must return [], not raise a KeyError -- use .get(value, 0) (an empty bitmap has no bits set).
• query_not must never use Python's ~ operator on a bitmap.

Real-world grounding

• DuckDB and ClickHouse both use bitmap-style representations for low-cardinality columns internally (ClickHouse's bitmapAnd/bitmapOr functions expose this exact operation directly in SQL): ClickHouse/ClickHouse

Real bitmap indexes at scale use compressed representations (Roaring bitmaps being the dominant modern one) since a raw one-bit-per-row bitmap over a billion-row table would be enormous if most values are rare -- but the core "one bitmap per value, combine with bitwise ops" idea is exactly what this exercise implements.