DSA Interview Prep · Lesson

Bit Masks: Set, Clear, Toggle, Check

Implement helpers to set, clear, toggle, and check individual bits, and apply bit masks to represent subsets in subset-enumeration problems.

Bit Masks: Set, Clear, Toggle, Check is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

What Are Bit Masks?

A bit mask is an integer used to select, modify, or test specific bits in another integer. The mask has 1s in the positions you care about and 0s elsewhere. Combined with bitwise operators, masks let you perform fine-grained bit operations without affecting other bits.

The four fundamental mask operations are: set (turn a bit on), clear (turn a bit off), toggle (flip a bit), and check (test whether a bit is 1). Each uses a different operator — OR, AND-NOT, XOR, and AND respectively — with the mask 1 << k.

# The four fundamental bit mask operations
def set_bit(n, k):    return n | (1 << k)       # OR to set
def clear_bit(n, k):  return n & ~(1 << k)      # AND-NOT to clear
def toggle_bit(n, k): return n ^ (1 << k)       # XOR to toggle
def check_bit(n, k):  return (n >> k) & 1       # shift+AND to check

n = 0b10110101  # 181
print(f'n = {bin(n)}')
print(f'set   bit 1: {bin(set_bit(n, 1))}')
print(f'clear bit 2: {bin(clear_bit(n, 2))}')
print(f'toggle bit 0: {bin(toggle_bit(n, 0))}')
print(f'check bit 4: {check_bit(n, 4)}')

Set Bit: Turning a Bit On

To set bit k (force it to 1 regardless of its current value), OR the number with the mask 1 << k. Since 0 OR 1 = 1 and 1 OR 1 = 1, the target bit becomes 1. All other bits are OR'd with 0, which leaves them unchanged.

Setting a bit is idempotent — calling it multiple times has the same effect as calling it once. If bit k is already 1, the result is unchanged. This property is important for flag management where you want to enable a feature without worrying about its current state.

def set_bit(n, k):
    mask = 1 << k
    return n | mask

# Set various bits
n = 0b00001010  # 10
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
    result = set_bit(n, k)
    print(f'Set bit {k}: {bin(result)} = {result}')

# Idempotence: setting already-set bit does nothing
n = 0b1111
print(f'\nAlready set: {bin(set_bit(n, 2))} = {bin(n)} (unchanged)')

# Setting multiple bits at once with a combined mask
mask = (1 << 0) | (1 << 2) | (1 << 4)  # bits 0, 2, 4
print(f'Set bits 0,2,4: {bin(0 | mask)} = {0 | mask}')

Clear Bit: Turning a Bit Off

To clear bit k (force it to 0 regardless of its current value), AND the number with the complement of the mask: n & ~(1 << k). The complement ~(1 << k) has all bits set to 1 except bit k, which is 0. AND-ing with 0 forces the target bit to 0; AND-ing with 1 preserves all other bits.

Like set, clear is idempotent. Clearing a bit that is already 0 leaves the number unchanged. In Python, ~(1 << k) works correctly for any k because Python handles the sign extension automatically — the complement has all higher bits set to 1 conceptually.

def clear_bit(n, k):
    mask = ~(1 << k)     # all 1s except bit k
    return n & mask

n = 0b11111111  # 255: all bits set
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
    result = clear_bit(n, k)
    print(f'Clear bit {k}: {bin(result)} = {result}')

# Clear multiple bits with combined mask complement
def clear_bits(n, positions):
    mask = 0
    for k in positions:
        mask |= (1 << k)
    return n & ~mask

result = clear_bits(0b11111111, [1, 3, 5, 7])
print(f'Clear bits 1,3,5,7: {bin(result)} = {result}')  # 0b01010101 = 85

Toggle Bit: Flipping a Bit

To toggle bit k (flip it from 0 to 1 or from 1 to 0), XOR the number with the mask 1 << k. XOR with 1 flips the bit; XOR with 0 leaves it unchanged. This is the fundamental property of XOR applied to a single bit.

Toggle is the only one of the four operations that is not idempotent — calling it twice returns to the original value. This makes it perfect for features that alternate between two states, such as a on/off switch or a boolean flag in a compact integer representation.

def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b10101010  # 170
print(f'Original:    {bin(n)}')
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # off->on: 10101011
print(f'Toggle bit 1: {bin(toggle_bit(n, 1))}')  # on->off: 10101000
print(f'Toggle bit 7: {bin(toggle_bit(n, 7))}')  # on->off: 00101010

# Toggle is its own inverse: two toggles = no change
result = toggle_bit(toggle_bit(n, 3), 3)
print(f'Double toggle bit 3: {bin(result)} == original {bin(n)}? {result == n}')

# Toggle all lower k bits
def toggle_lower_k(n, k):
    mask = (1 << k) - 1   # k ones in the lowest positions
    return n ^ mask

print(f'Toggle lower 4 bits of {bin(n)}: {bin(toggle_lower_k(n, 4))}')

Check Bit: Testing Whether a Bit Is Set

To check if bit k is set, right-shift n by k positions and AND with 1: (n >> k) & 1. This brings bit k to position 0 and masks off all higher bits, leaving 0 (bit k was 0) or 1 (bit k was 1). Alternatively, use bool(n & (1 << k)) for a True/False result.

Checking a bit is non-destructive — it does not modify n. You can check multiple bits by shifting and masking each position independently. This is the basis for iterating over the bit representation of a number, which is used in subset enumeration and dynamic programming with bitmask states.

def check_bit(n, k):
    return (n >> k) & 1

def is_bit_set(n, k):
    return bool(n & (1 << k))

n = 0b10110101  # 181
print(f'n = {bin(n)} = {n}')
for k in range(8):
    print(f'Bit {k}: {check_bit(n, k)} ({"set" if check_bit(n, k) else "clear"})')

# Count set bits using check_bit
def count_set_bits(n):
    return sum(check_bit(n, k) for k in range(n.bit_length()))

print(f'\nSet bits in {n}: {count_set_bits(n)}')

# Get bit representation as list (LSB first)
def to_bit_list(n, width=8):
    return [check_bit(n, k) for k in range(width)]

print(f'Bit list (LSB first): {to_bit_list(n)}')

Bit Masks for Subset Representation

An integer with n bits can represent a subset of an n-element set: bit k is 1 if element k is in the subset, 0 otherwise. This compresses a subset into a single integer, enabling O(1) operations: membership test (mask & (1 << k)), adding an element (mask | (1 << k)), removing an element (mask & ~(1 << k)), and set union/intersection (mask1 | mask2 and mask1 & mask2).

With n elements, there are 2^n possible subsets, each uniquely represented by an n-bit integer from 0 to 2^n - 1. Iterating over all integers from 0 to 2^n - 1 enumerates all subsets.

# Subset representation with bitmasks
elements = ['A', 'B', 'C', 'D']
n = len(elements)

def subset_from_mask(mask):
    return [elements[k] for k in range(n) if (mask >> k) & 1]

# Enumerate all 2^n subsets
print('All subsets:')
for mask in range(1 << n):   # 0 to 15 for n=4
    print(f'  {mask:04b}: {subset_from_mask(mask)}')

# Set operations
mask_ab = 0b0011   # {A, B}
mask_bc = 0b0110   # {B, C}
print(f'\nUnion:        {subset_from_mask(mask_ab | mask_bc)}')
print(f'Intersection: {subset_from_mask(mask_ab & mask_bc)}')
print(f'Difference A\\B: {subset_from_mask(mask_ab & ~mask_bc & 0b1111)}')

Iterating Over All Subsets of a Mask

In bitmask dynamic programming, you often need to iterate over all subsets of a given mask. A common trick: start with sub = mask and iterate with sub = (sub - 1) & mask until sub reaches 0. Each iteration yields a different submask. This is O(3^n) total over all masks because each element can be in the outer mask but not the submask, in both, or in neither.

This technique appears in problems like 'partition array into subsets with equal XOR' or 'find the maximum AND of any subset'. The ability to enumerate submasks efficiently is a hallmark of advanced bitmask DP.

def all_submasks(mask):
    submasks = []
    sub = mask
    while sub > 0:
        submasks.append(sub)
        sub = (sub - 1) & mask
    submasks.append(0)  # empty subset
    return submasks

mask = 0b1011   # {0, 1, 3}
elements = ['A', 'B', 'C', 'D']
def show(m): return '{' + ','.join(elements[k] for k in range(4) if (m>>k)&1) + '}'

print(f'All submasks of {bin(mask)} = {show(mask)}:')
for sub in all_submasks(mask):
    print(f'  {bin(sub):6s}: {show(sub)}')
print(f'Total: {len(all_submasks(mask))} submasks (should be 2^{bin(mask).count("1")} = {2**bin(mask).count("1")})')

Bitmask DP: Traveling Salesman Preview

Bitmask DP solves problems where the state includes a subset of visited items. The classic example is the Traveling Salesman Problem (TSP): find the minimum cost tour visiting n cities. The state is dp[mask][city] = minimum cost to visit the cities in mask, ending at city. With n cities, there are 2^n × n states, giving O(n^2 × 2^n) time — feasible for n ≤ 20.

The mask serves as a compressed visited-set. Setting, clearing, and checking bits corresponds to visiting, leaving, and querying cities. This is bitmask DP's core: use bits as a compact set for the state.

# TSP with bitmask DP
import sys

def tsp(dist):
    n = len(dist)
    INF = float('inf')
    # dp[mask][v] = min cost to reach v having visited cities in mask
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0   # start at city 0, only city 0 visited (mask=1=0b0001)

    for mask in range(1 << n):
        for v in range(n):
            if dp[mask][v] == INF: continue
            if not (mask >> v) & 1: continue  # v must be in mask
            for u in range(n):
                if (mask >> u) & 1: continue  # u must not be visited
                new_mask = mask | (1 << u)
                dp[new_mask][u] = min(dp[new_mask][u], dp[mask][v] + dist[v][u])

    full_mask = (1 << n) - 1
    return min(dp[full_mask][v] + dist[v][0] for v in range(1, n))

dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
print('TSP minimum tour cost:', tsp(dist))  # should be 80

Multi-Bit Masking: Extracting a Field

Sometimes you need to extract not just a single bit but a multi-bit field — a contiguous range of bits. To extract bits from position start to start+length-1, create a mask of length consecutive 1-bits: mask = (1 << length) - 1, then (n >> start) & mask.

This technique is used in parsing packed integer formats (like IP addresses, pixel data, or hardware registers) where several small values are stored in one integer. For example, a 16-bit RGB565 pixel stores red in bits 15-11, green in 10-5, and blue in 4-0.

def extract_field(n, start, length):
    mask = (1 << length) - 1   # e.g., length=3 => mask=0b111
    return (n >> start) & mask

# RGB565 pixel format: RRRRRGGGGGGBBBBB
pixel = 0b1111100111001000  # 63432
red   = extract_field(pixel, 11, 5)   # bits 15-11
green = extract_field(pixel, 5, 6)    # bits 10-5
blue  = extract_field(pixel, 0, 5)    # bits 4-0
print(f'Pixel: {hex(pixel)}')
print(f'Red:   {red}   ({bin(red)})')
print(f'Green: {green} ({bin(green)})')
print(f'Blue:  {blue}  ({bin(blue)})')

# Packing values back
def pack_rgb565(r, g, b):
    return (r << 11) | (g << 5) | b

packe = pack_rgb565(red, green, blue)
print(f'Repacked: {hex(packed) if (packed := pack_rgb565(red,green,blue)) else 0}')

Bit Masks in Interview Problems

Bit masks commonly appear in these interview problem types:

Subset enumeration: iterate all 2^n subsets using masks 0 to 2^n-1
State compression DP: encode a set of visited nodes/items as a bitmask in the DP state
Permission systems: combine READ/WRITE/EXECUTE flags with OR, check with AND
Grid visited tracking: for small grids, pack visited cells into one integer

A key indicator that bitmasks are useful: the problem involves a small set (n ≤ 20 items) and you need to track combinations of membership. Larger sets require different representations.

# Subset sum with bitmask enumeration
def subset_sum_exists(nums, target):
    n = len(nums)
    for mask in range(1 << n):
        total = sum(nums[k] for k in range(n) if (mask >> k) & 1)
        if total == target:
            subset = [nums[k] for k in range(n) if (mask >> k) & 1]
            print(f'Found subset {subset} summing to {target}')
            return True
    return False

subset_sum_exists([3, 1, 4, 1, 5], 10)  # finds a subset summing to 10

# Check if permutation covers all required elements (bitmask approach)
required = 0b11111  # need all 5 elements
visited  = 0b01101  # visited elements 0, 2, 3
all_visited = (visited & required) == required
print(f'All required visited: {all_visited}')  # False: missing bits 1 and 4

Efficient Bit Enumeration Tricks

When iterating over the set bits of a mask, two common techniques are used. The shift-and-check method: shift right and check the LSB. The lowest-set-bit isolation method: isolate the lowest set bit with n & -n, process it, then clear it with n &= n - 1. The second method only visits set bits and is faster when the mask is sparse.

In Python, you can also use bin(n).count('1') or n.bit_count() (3.10+) for popcount. For the bit-position of each set bit, use n.bit_length() - 1 for the highest set bit.

# Iterate over set bit positions
def set_bit_positions(n):
    positions = []
    k = 0
    while n:
        if n & 1:
            positions.append(k)
        n >>= 1
        k += 1
    return positions

# Faster: use lowest-set-bit isolation
def set_bit_positions_fast(n):
    positions = []
    while n:
        lsb = n & -n           # isolate lowest set bit
        k = lsb.bit_length() - 1  # position of that bit
        positions.append(k)
        n &= n - 1             # clear lowest set bit
    return positions

mask = 0b10110101
print(f'Set positions (naive): {set_bit_positions(mask)}')
print(f'Set positions (fast):  {set_bit_positions_fast(mask)}')
print(f'Bit count: {bin(mask).count("1")}')
print(f'Highest set bit: {mask.bit_length() - 1}')

Quick Check

Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.

Lesson Recap

In this lesson you learned: the four fundamental bit mask operations are set (OR), clear (AND-NOT), toggle (XOR), and check (shift-AND), integers can represent subsets where each bit encodes membership of one element, enabling 2^n subset enumeration, and multi-bit field extraction and bitmask DP use the same masking principles for more complex state encoding. Next up we explore counting bits, missing numbers, and bit reversal using the techniques from this and the previous lesson.

Frequently asked questions

Is the “Bit Masks: Set, Clear, Toggle, Check” lesson free?

Yes — the full text of “Bit Masks: Set, Clear, Toggle, Check” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.

What will I learn in “Bit Masks: Set, Clear, Toggle, Check”?

Implement helpers to set, clear, toggle, and check individual bits, and apply bit masks to represent subsets in subset-enumeration problems. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start DSA Interview Prep?

No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Bit Masks: Set, Clear, Toggle, Check” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this DSA Interview Prep lesson?

Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

Bitwise Operators: AND, OR, XOR, NOT, Shifts
Single Number and XOR Properties
Bit Masks: Set, Clear, Toggle, Check
Counting Bits, Missing Number, and Reverse Bits

← Back to DSA Interview Prep