AlgoScope

Bitmask

algorithmintermediateTime O(1) per operation, O(2^n) to enumerateSpace O(1)

An integer is a row of booleans, so it can be a set: bit i on means element i is in. Add, remove and test are single bit operations, the set fits in a register, and counting from 0 to 2^n - 1 visits every subset exactly once.

100201302403

4 elements, so 4 bits. Bit i stands for element i, and the mask starts at 0: the empty set. Bits are read right to left, so element 0 is the rightmost bit.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. Mask is 0101. Is element 2, value 30, in the set?

    • In the set
    • Not in the set

    Answer: In the set. Bit 2, counting from the right, is 1. mask and (1 shl 2) is not zero.

  2. Mask is 0101. Is element 1, value 20, in the set?

    • In the set
    • Not in the set

    Answer: Not in the set. Bit 1, counting from the right, is 0. mask and (1 shl 1) is zero.

  3. Mask is 0011. Is element 2, value 30, in the set?

    • In the set
    • Not in the set

    Answer: Not in the set. Bit 2, counting from the right, is 0. mask and (1 shl 2) is zero.

How it runs, step by step

  1. 4 elements, so 4 bits. Bit i stands for element i, and the mask starts at 0: the empty set. Bits are read right to left, so element 0 is the rightmost bit.

    An empty set over 4 elements, stored as a mask of 4 bits. Running 7 operations.

  2. add 2: mask or (1 shl 2). Bit 2 turns on. The set is {30}.

    add element 2. The set is now {30}.

  3. add 0: mask or (1 shl 0). Bit 0 turns on. The set is {10, 30}.

    add element 0. The set is now {10, 30}.

  4. has 2: mask and (1 shl 2) is not zero, so element 2 is in.

    Element 2 is in the set.

  5. has 1: mask and (1 shl 1) is zero, so element 1 is out.

    Element 1 is not in the set.

  6. toggle 1: mask xor (1 shl 1). Bit 1 flips on. The set is {10, 20, 30}.

    toggle element 1. The set is now {10, 20, 30}.

  7. remove 2: mask and not (1 shl 2). Bit 2 turns off. The set is {10, 20}.

    remove element 2. The set is now {10, 20}.

  8. has 2: mask and (1 shl 2) is zero, so element 2 is out.

    Element 2 is not in the set.

  9. Final mask 0011 = 3, the set {10, 20}. Every operation was one bit instruction, and the whole set fits in one integer.

    The final set is {10, 20}, mask 3.

Remember

  • 1 shl i is the mask with only bit i on. Or adds, and-not removes, xor toggles, and tests.
  • Masks 0 to 2^n - 1 are the 2^n subsets. Fine up to about n = 20, hopeless beyond.
  • sub = (sub - 1) and mask walks every submask of mask, high to low, without repeats.

Topics covered

Related

Where this is used

GamesBitboards in chess engines

A chessboard has 64 squares and a 64-bit integer has 64 bits, so an engine like Stockfish keeps one integer per piece type: bit 12 on means a piece of that type stands on square 12. Shifting the white pawn board left by 8 advances every pawn one rank in a single instruction, and anding the result with the complement of the occupied board drops the blocked ones. Generating moves for a whole army becomes a handful of shifts and masks instead of a loop over squares.

Operating systemsLinux open flags and file permissions

open(2) packs its options into one int: O_CREAT, O_APPEND, O_TRUNC and O_NONBLOCK are independent bits ored together, and the kernel tests each with a single and instead of parsing a list of options. The low two bits are not a set - they are a small field holding O_RDONLY, O_WRONLY or O_RDWR, and O_RDONLY is 0, so that part is read with a mask and a compare rather than a bit test. Permissions are pure bits again: chmod stores read, write and execute for owner, group and other as nine of them, which is why 0644 is a readable way to write a set, and a new flag costs a bit rather than a new argument.

DatabasesFilter bitsets in Lucene and Elasticsearch

Lucene stores the set of documents matching a filter as a bitset with one bit per document in the segment, so combining two filters is a word-at-a-time and rather than a merge of two sorted id lists. Intersecting a million documents touches about sixteen thousand 64-bit words, which the CPU chews through at memory speed. Elasticsearch caches these bitsets for filters it sees repeatedly, and stores sparse ones as roaring bitmaps so empty regions cost nothing.

OptimisationHeld-Karp exact route planning

Held-Karp solves the travelling salesman problem by asking, for every set of stops already visited and every stop you are standing on, the cheapest way to have got there. The set of visited stops is the mask, so the table is an ordinary array indexed by that integer and each transition just turns one more bit on. It runs in O(2^n n^2), which is why exact tours are practical up to roughly twenty stops and heuristics take over above that.

Why it works this way

Why (sub - 1) and mask walks the submasks

Subtracting 1 clears the lowest set bit of sub and turns every bit below it on. Anding with mask discards the bits that were never in mask, and what is left is the next submask down in numeric order. Placement of the zero check matters: a loop written while (sub != 0) never visits the empty set, and a loop with no break at all wraps, because 0 - 1 is all ones and all ones and mask is mask again.

1 shl i stops working at the width of the word

Kotlin and Java take the shift count modulo the width of the type, so 1 shl 32 is 1 rather than 0 and a loop that runs to n = 32 silently starts writing over bit 0 again. In C the same shift is undefined behaviour that usually does the same thing on x86. 1 shl 31 is also negative, since bit 31 is the sign bit. For more than 31 elements use 1L shl i and a Long, which gets you to 63.

Remove must be and-not, not xor

xor takes the element out when it is there and puts it in when it is not, so mask xor (1 shl i) is only a remove if you already know bit i is on. mask and (1 shl i).inv() clears the bit either way, which is what you want because most code removes without checking first. or has the matching property on the other side: adding an element that is already in the set changes nothing.

Every submask of every mask costs 3^n, not 4^n

There are 2^n masks and a mask with k bits set has 2^k submasks, so the total looks like it could be 2^n times 2^n. It is not: summing C(n, k) 2^k over k gives 3^n, because each element is independently outside the mask, inside the mask but outside the submask, or inside both. At n = 16 that is 43 million steps instead of 4.3 billion, which is the difference between a loop that finishes and one that does not.

Read more

Next up