0Pricing
Competitive Programming Academy · Lesson

Bitmasks as Tiny Sets

Represent subsets as integers.

An Integer as a Set

A single integer can stand in for a whole set: bit i being 1 means element i is in. This packs subsets into one tiny, fast value. 🎒

The Empty and Full Sets

The number 0 is the empty set, while a value with the lowest n bits all on means every element is present.

empty = 0
full = (1 << 4) - 1  # 0b1111, four elements

All lessons in this course

  1. AND, OR, XOR & Shifts
  2. Set, Clear & Toggle a Bit
  3. Count Bits and Lowest Set Bit
  4. Bitmasks as Tiny Sets
← Back to Competitive Programming Academy