Bit Masking

Not Started

Bit masking is a way to use a single integer as a collection of on/off switches. Each bit in the integer acts like a checkbox: 1 means "on" or "present", 0 means "off" or "absent".

This is useful when you need to track which items from a small set are "active". For example, which letters appear in a word, or which nodes have been visited.

The Core Idea

Think of bits as slots: An integer like 13 in binary is 1101. Reading right to left, slots 0, 2, and 3 are "on" (value 1). Slot 1 is "off" (value 0).

Each slot can represent something: Slot 0 could mean "contains letter a", slot 1 could mean "contains letter b", and so on. If the bit is 1, the item is present.

Why use this? Checking if two sets overlap becomes a single operation instead of nested loops. This makes certain problems much faster.

Binary Refresher

Computers store numbers in binary (base 2). Each digit is called a bit and can only be 0 or 1. The rightmost bit is position 0, and positions increase as you move left.

Decimal 5 = binary 101 = (1 x 4) + (0 x 2) + (1 x 1)

Decimal 13 = binary 1101 = (1 x 8) + (1 x 4) + (0 x 2) + (1 x 1)

Powers of 2: Position 0 = 1, Position 1 = 2, Position 2 = 4, Position 3 = 8, and so on.

The Left Shift Operator

The expression 1 << n creates a number with only bit n set to 1. This is your main tool for targeting a specific bit position.

1 << 0 = 1 (binary: 0001) - bit 0 is on

1 << 1 = 2 (binary: 0010) - bit 1 is on

1 << 2 = 4 (binary: 0100) - bit 2 is on

1 << 3 = 8 (binary: 1000) - bit 3 is on

The Three Key Operators

Once you can target a bit with left shift, you combine it with these operators to manipulate your mask:

OR (|) turns bits ON: Use mask | (1 << n) to set bit n to 1. Think of it as "add to set".

AND (&) checks bits: Use mask & (1 << n) to test if bit n is set. Non-zero result means yes.

AND with NOT (& ~) turns bits OFF: Use mask & ~(1 << n) to clear bit n. Think of it as "remove from set".

Set a Bit (Add to Set)

To add an item to your set, turn its bit ON using OR. Here is a step-by-step example:

Goal: Add item 3 to an empty set

Step 1: Start with mask = 0 (binary: 0000) - empty set

Step 2: Create a bit at position 3: 1 << 3 = 8 (binary: 1000)

Step 3: OR them together: 0000 | 1000 = 1000

Result: mask = 8 - bit 3 is now ON, meaning item 3 is in the set

mask = 0         # empty set
mask |= 1 << 3  # add item 3 -> mask is now 8 (binary: 1000)
mask |= 1 << 1  # add item 1 -> mask is now 10 (binary: 1010)

int mask = 0;        // empty set
mask |= 1 << 3;  // add item 3 -> mask is now 8 (binary: 1000)
mask |= 1 << 1;  // add item 1 -> mask is now 10 (binary: 1010)

int mask = 0;        // empty set
mask |= 1 << 3;  // add item 3 -> mask is now 8 (binary: 1000)
mask |= 1 << 1;  // add item 1 -> mask is now 10 (binary: 1010)

int mask = 0;        // empty set
mask |= 1 << 3;  // add item 3 -> mask is now 8 (binary: 1000)
mask |= 1 << 1;  // add item 1 -> mask is now 10 (binary: 1010)

Check a Bit (Membership Test)

To check if an item is in your set, use AND. If the result is non-zero, the item is present.

Goal: Check if item 3 is in the set (mask = 10, binary: 1010)

Step 1: Create a bit at position 3: 1 << 3 = 8 (binary: 1000)

Step 2: AND them: 1010 & 1000 = 1000 (non-zero!)

Result: Non-zero means YES, item 3 is in the set

Compare: Check if item 2 is in the set (mask = 10, binary: 1010)

Step 1: Create a bit at position 2: 1 << 2 = 4 (binary: 0100)

Step 2: AND them: 1010 & 0100 = 0000 (zero!)

Result: Zero means NO, item 2 is not in the set

mask = 10  # binary: 1010 (items 1 and 3 are in the set)

if mask & (1 << 3):  # check item 3
    print("item 3 is present")  # this runs

if mask & (1 << 2):  # check item 2
    print("item 2 is present")  # this does NOT run

int mask = 10;  // binary: 1010 (items 1 and 3 are in the set)

if (mask & (1 << 3))  // check item 3
    cout << "item 3 is present";  // this runs

if (mask & (1 << 2))  // check item 2
    cout << "item 2 is present";  // this does NOT run

int mask = 10;  // binary: 1010 (items 1 and 3 are in the set)

if ((mask & (1 << 3)) != 0)  // check item 3
    Console.WriteLine("item 3 is present");  // this runs

if ((mask & (1 << 2)) != 0)  // check item 2
    Console.WriteLine("item 2 is present");  // this does NOT run

int mask = 10;  // binary: 1010 (items 1 and 3 are in the set)

if ((mask & (1 << 3)) != 0)  // check item 3
    System.out.println("item 3 is present");  // this runs

if ((mask & (1 << 2)) != 0)  // check item 2
    System.out.println("item 2 is present");  // this does NOT run

Comparing Two Sets (The Power Move)

The real power of bit masking is comparing two sets instantly. If you AND two masks together:

Result is zero: The sets have NO items in common

Result is non-zero: The sets share at least one item

Example: Do sets {1, 3} and {2, 3} share any items?

Set A = {1, 3} has mask 1010 (bits 1 and 3 are on)

Set B = {2, 3} has mask 1100 (bits 2 and 3 are on)

1010 & 1100 = 1000 (non-zero!)

Result: Yes, they share item 3

Worked Example: Letter Set Comparison

A classic problem: given two words, do they share any letters? With bit masking, this becomes trivial.

Idea: Use bit 0 for 'a', bit 1 for 'b', bit 2 for 'c', and so on up to bit 25 for 'z'

Build a mask: For each letter in the word, set its corresponding bit

Compare: AND the two masks. Zero means no shared letters.

Example: Do "abc" and "xyz" share any letters?

"abc" sets bits 0, 1, 2 (for a, b, c)

"xyz" sets bits 23, 24, 25 (for x, y, z)

AND them: no overlapping bits, result is 0

Result: No shared letters

Example: Do "abc" and "cde" share any letters?

"abc" sets bits 0, 1, 2

"cde" sets bits 2, 3, 4

AND them: bit 2 is set in both, result is non-zero

Result: They share 'c'

def word_to_mask(word):
    mask = 0
    for ch in word:
        mask |= 1 << (ord(ch) - ord('a'))
    return mask

def share_letters(word1, word2):
    return word_to_mask(word1) & word_to_mask(word2) != 0

# Example
print(share_letters("abc", "xyz"))  # False
print(share_letters("abc", "cde"))  # True (share 'c')

int wordToMask(string& word) {
    int mask = 0;
    for (char c : word)
        mask |= 1 << (c - 'a');
    return mask;
}

bool shareLetters(string& word1, string& word2) {
    return (wordToMask(word1) & wordToMask(word2)) != 0;
}

// Example
cout << shareLetters("abc", "xyz");  // 0 (false)
cout << shareLetters("abc", "cde");  // 1 (true, share 'c')

int WordToMask(string word) {
    int mask = 0;
    foreach (char c in word)
        mask |= 1 << (c - 'a');
    return mask;
}

bool ShareLetters(string word1, string word2) {
    return (WordToMask(word1) & WordToMask(word2)) != 0;
}

// Example
Console.WriteLine(ShareLetters("abc", "xyz"));  // False
Console.WriteLine(ShareLetters("abc", "cde"));  // True (share 'c')

int wordToMask(String word) {
    int mask = 0;
    for (char c : word.toCharArray())
        mask |= 1 << (c - 'a');
    return mask;
}

boolean shareLetters(String word1, String word2) {
    return (wordToMask(word1) & wordToMask(word2)) != 0;
}

// Example
System.out.println(shareLetters("abc", "xyz"));  // false
System.out.println(shareLetters("abc", "cde"));  // true (share 'c')