ReviseAlgo Logo

Bit Manipulation

Bitmasking

Master Bitmasking: subset representation using integers, bitmask edits, and submask enumeration.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What is Bitmasking?

Bitmasking is the practice of representing a set of elements (a subset) using a single integer. Each bit in the integer acts as a boolean flag: 1 indicates the element at that index is present in the subset, and 0 indicates it is absent.

Why study it?

Bitmasking is essential for NP-hard optimization problems (like the Travelling Salesman Problem) because it allows you to store a set state inside a single integer. This integer can then be used directly as a key in DP memoization tables, reducing complexity.

Where is it Used?

  • File System Permissions: POSIX permissions check read/write/execute status by treating permissions as a 3-bit mask.
  • Game Engine States: Tracking active inventory items or completed quest states in a single integer flag word.

    • 2. Mental Model: The Keychain

    Imagine a keychain that can hold up to 5 keys:

  • Having or not having the i-th key is a single binary status (1 or 0).
  • The entire keychain can be represented by a single 5-bit binary number (e.g. 10100 means you have key 4 and key 2, but lack keys 3, 1, and 0).
  • Adding a key, dropping a key, or checking if you carry a key is done in a single operation without search loops.

    • 3. Core Bitmask Operations & Subset Iterations

    For a set of size N, subsets are mapped to integer values 0 (empty set) to 2^N - 1 (all elements present).

    1. Operations on Bitmasks

  • Add element i: mask = mask | (1 << i)
  • Remove element i: mask = mask & ~(1 << i)
  • Check if element i is present: (mask & (1 << i)) != 0

    • 2. Enumerating Subsets (Power Set)

    To generate all subsets of a set of size N, iterate from 0 to (1 << N) - 1.

    3. Enumerating all Submasks of a specific Mask

    To iterate through all subsets of a given bitmask mask efficiently:

    This runs in O(3^N) overall time when summing over all possible masks, which is significantly faster than the naive O(4^N) search.

    4. Visualizing Bitmask Mappings

    Subsets of set ['A', 'B', 'C'] (size N = 3, indices 2, 1, 0):

    Bitmask (Binary)Bitmask (Decimal)Evaluation LogicRepresented Subset
    0000No bits set[] (Empty Set)
    0011Bit 0 set['A']
    0102Bit 1 set['B']
    0113Bits 0 and 1 set['A', 'B']
    1004Bit 2 set['C']
    1106Bits 1 and 2 set['B', 'C']
    1117All bits set['A', 'B', 'C']

    5. Real-World Examples

  • Subnet network ranges routing: Matching address subsets using network bitmasks.
  • SQL Database Indexing: Storing column attributes (nullability, indexing status) inside a single byte flag.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test state encoding:
  • "Write an algorithm to generate all subsets of an array." -> While backtracking is standard, explain that bitmasking provides a non-recursive iterative alternative using integers 0 to 2^N - 1.
  • "How do you represent state in Travelling Salesman DP?" -> Explain that you track visited nodes using a bitmask of size N (requiring values up to (1 << N) - 1), yielding state coordinates dp[mask][currentNode].

    • Common Mistakes

    Warning: 1. Overflowing 32-bit Integer limits: Using standard 1 << i when i >= 31. This causes integer overflow because standard integers are 32-bit signed in Java/C++. Use 64-bit longs: 1L << i or 1LL << i.
    > 2. Wrong Loop Limits: Iterating with mask <= (1 << N). Since values start at 0, the loop should bound strictly under (1 << N) (representing 2^N total states).

    7. Summary

  • Add Element: mask | (1 << i).
  • Remove Element: mask & ~(1 << i).
  • Check Presence: (mask & (1 << i)) != 0.
  • Subset Enumeration: Iterate 0 to (1 << N) - 1.

    • 8. Quiz

    Question 1: If mask = 5 (binary 101), how do we check if element 1 is present in the subset? Answer: Evaluate (mask & (1 << 1)). Since 1 << 1 is 2 (binary 010), 5 & 2 yields 0. This indicates element 1 is absent.
    Question 2: What is the maximum set size N that can be safely mapped to a standard 32-bit signed integer bitmask? Answer: N = 30. Using 31 bits conflicts with the signed flag bit (changing the value to negative bounds), so we limit signed 32-bit masks to size 30.
    Question 3: How do you represent the union of two subsets represented by bitmasks A and B? Answer: A | B (bitwise OR combines the elements of both subsets).
    Question 4: True or False: Submask iteration loop 'sub = (sub - 1) & mask' terminates when sub reaches 0. Answer: True. The step sub = (sub - 1) & mask decrements and masks, eventually yielding 0 which terminates the loop.
    Question 5: What is the intersection of two subsets represented by bitmasks A and B? Answer: A & B (bitwise AND isolates elements present in both subsets).