DSA Masterclass: The Bitmasking & XOR Blueprint

1. Why Bitmasking?

A "mask" is just an integer where each bit represents a boolean state.

Example: int mask = 5 (Binary 101) means "The 0th and 2nd items are selected, but the 1st is not."
Why use it?: It allows you to pass an entire "Set" of items as a single integer, which is mandatory for Bitmask DP (e.g., Travelling Salesman Problem).

2. The Golden Operators Table

Operation	Java Code	Mental Model
Set i-th bit	`mask \| (1 << i)`	Turn switch ON
Unset i-th bit	`mask & ~(1 << i)`	Turn switch OFF
Flip i-th bit	`mask ^ (1 << i)`	Toggle switch
Check i-th bit	`(mask & (1 << i)) != 0`	Is switch ON?
All Bits ON	`(1 << n) - 1`	Fill a set of size N

3. XOR: The Magical Operator

XOR (^) is the secret to many elite interview questions because of these properties:

x ^ x = 0 (Self-cancellation)
x ^ 0 = x (Identity)
x ^ y = y ^ x (Commutative)

Interview Pattern: "Every number appears twice except one."
Solution: XOR everything. The result is the unique number.

4. Problem Pattern: Power Set Generation

To generate all subsets of an array of size $N$, you simply iterate from $0$ to $2^N - 1$. Each number is a bitmask of a unique subset.

public List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < (1 << n); i++) { // From 0 to 2^n - 1
        List<Integer> sub = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) != 0) { // If bit j is set in mask i
                sub.add(nums[j]);
            }
        }
        res.add(sub);
    }
    return res;
}

5. Interview Discussion: The "Aha!" Moment

Interviewer: "How do you store visited states in a grid of 15 cells efficiently?"
You: "I can use a 15-bit integer as a bitmask. This allows me to use a simple integer array or HashMap for memoization, which is much faster than strings or objects."