Bit Masks

March 2026 · 28 min read

A bit mask is a pattern of bits used to select, modify, or test specific bits in a value. Masking is the most practical everyday application of bit manipulation. Understanding masks unlocks everything from Unix file permissions to network subnet masks to game engine feature flags.

Creating Masks

Single Bit Mask

uint32_t mask = 1u << i;  // bit i set, all others 0
// 1 << 0  = 0b00000001
// 1 << 3  = 0b00001000
// 1 << 7  = 0b10000000
// 1 << 31 = 0x80000000  (use 1u to avoid signed overflow)

Lower n Bits Mask

uint32_t low_mask(int n) {
    return (1u << n) - 1;
}
// low_mask(4) = 0b00001111 = 0xF
// low_mask(8) = 0b11111111 = 0xFF

Range Mask: Bits i through j

// Mask with bits [low, high] set (inclusive):
uint32_t range_mask(int low, int high) {
    int width = high - low + 1;
    return low_mask(width) << low;
}

// Example: bits 2 through 5
//   low_mask(4) = 0b00001111
//   << 2        = 0b00111100
// Bits 2,3,4,5 are set

Extracting Bit Fields

To extract bits [low, high] from a value, shift right by low then mask off the field width:

uint32_t extract_field(uint32_t value, int low, int width) {
    return (value >> low) & low_mask(width);
}

// Example: extract bits 4-7 from 0xABCD
// 0xABCD = 0b1010 1011 1100 1101
// >> 4   = 0b0000 1010 1011 1100
// & 0xF  = 0b0000 0000 0000 1100 = 0xC

uint32_t extract_field_with_range_mask(uint32_t value, int low, int high) {
    return (value & range_mask(low, high)) >> low;
}

Setting Bit Fields

uint32_t set_field(uint32_t value, int low, int width, uint32_t field) {
    uint32_t mask = ((1u << width) - 1) << low;
    value &= ~mask;                    // clear the field
    value |= (field << low) & mask;    // set the new value
    return value;
}

Real-World: Unix File Permissions

// rwxrwxrwx = 9 bits
constexpr uint16_t OWNER_R = 1 << 8;  // 0b100000000
constexpr uint16_t OWNER_W = 1 << 7;  // 0b010000000
constexpr uint16_t OWNER_X = 1 << 6;  // 0b001000000
constexpr uint16_t GROUP_R = 1 << 5;
constexpr uint16_t GROUP_W = 1 << 4;
constexpr uint16_t GROUP_X = 1 << 3;
constexpr uint16_t OTHER_R = 1 << 2;
constexpr uint16_t OTHER_W = 1 << 1;
constexpr uint16_t OTHER_X = 1 << 0;

uint16_t perms = OWNER_R | OWNER_W | OWNER_X | GROUP_R | GROUP_X | OTHER_R | OTHER_X;
// perms = 0b111101101 = 0755 in octal

// Check: can group write?
bool group_writable = perms & GROUP_W;  // false

// Grant group write:
perms |= GROUP_W;

// Revoke other execute:
perms &= ~OTHER_X;

Real-World: Feature Flags

enum Features : uint32_t {
    LOGGING    = 1 << 0,
    ENCRYPTION = 1 << 1,
    COMPRESSION = 1 << 2,
    CACHING    = 1 << 3,
    TELEMETRY  = 1 << 4,
};

uint32_t config = LOGGING | ENCRYPTION | CACHING;

// Check if encryption is enabled:
if (config & ENCRYPTION) { /* ... */ }

// Enable compression:
config |= COMPRESSION;

// Disable logging:
config &= ~LOGGING;

// Toggle telemetry:
config ^= TELEMETRY;

Real-World: IP Subnet Masks

// A /24 subnet mask: 255.255.255.0 = 0xFFFFFF00
uint32_t subnet_mask = ~((1u << (32 - 24)) - 1);
// = ~(0xFF) = 0xFFFFFF00

// Get network address from IP and mask:
uint32_t ip      = 0xC0A80164;  // 192.168.1.100
uint32_t network = ip & subnet_mask; // 192.168.1.0

// Get host part:
uint32_t host = ip & ~subnet_mask;   // 0.0.0.100

Masks as Set Representation

An $n$-bit integer can represent any subset of an $n$-element set. Each bit position corresponds to an element: 1 means "in the set," 0 means "not in the set."

// Elements: {a, b, c, d} → bits {0, 1, 2, 3}
// Set {a, c} = 0b0101 = 5
// Set {b, d} = 0b1010 = 10

uint32_t setA = 0b0101, setB = 0b1010;

uint32_t unionAB     = setA | setB;   // {a,b,c,d} = 0b1111
uint32_t intersect   = setA & setB;   // {} = 0b0000
uint32_t difference  = setA & ~setB;  // {a,c} = 0b0101
uint32_t symDiff     = setA ^ setB;   // {a,b,c,d} = 0b1111
bool isSubset        = (setA & setB) == setA;  // false
int cardinality      = __builtin_popcount(setA); // 2

Competitive Programming Toolkit

Iterating Subsets of a Mask

A mask s is a submask of m when every set bit of s is also set in m. Equivalently, (s & m) == s. If m = 0b10110, then 0b10010 is a submask, but 0b01001 is not because bit 0 is absent from m.

Scanning every integer from m down to zero and testing the subset condition wastes work whenever m is sparse. The standard loop jumps directly from one valid non-empty submask to the next:

for (uint32_t s = m; s != 0; s = (s - 1) & m) {
    // s is a non-empty subset of m
}

Why (s - 1) & m Finds the Next Submask

The transition has two separate jobs:

1. s - 1 clears the lowest set bit of s and changes every lower bit to 1. Higher bits stay unchanged.
2. & m removes any newly created 1-bits that are not allowed by m.

The remaining lower positions are filled with every bit that is allowed by m. Therefore the result is the largest valid submask strictly smaller than s. The sequence decreases at every step, never repeats a mask, and cannot skip a valid submask between two consecutive values.

Worked Bit Trace

Let m = 0b10110. Its three set bits represent a set with three elements, so it has $2^3 = 8$ submasks, including the empty mask. The non-empty loop visits the other seven in descending numeric order:

m = 10110

s = 10110
    (10110 - 1) & 10110 = 10101 & 10110 = 10100
s = 10100
    (10100 - 1) & 10110 = 10011 & 10110 = 10010
s = 10010
    (10010 - 1) & 10110 = 10001 & 10110 = 10000
s = 10000
    (10000 - 1) & 10110 = 01111 & 10110 = 00110
s = 00110
    (00110 - 1) & 10110 = 00101 & 10110 = 00100
s = 00100
    (00100 - 1) & 10110 = 00011 & 10110 = 00010
s = 00010
    (00010 - 1) & 10110 = 00001 & 10110 = 00000

stop: s == 0

The transition from 10000 to 00110 is the most informative step. Subtracting one produces 01111; masking by 10110 keeps only the lower positions permitted by m, producing the largest remaining valid submask.

Including the Empty Submask

The empty set is often a valid DP choice. An explicit break processes s == 0 exactly once and avoids evaluating s - 1 after zero:

for (uint32_t s = m; ; s = (s - 1) & m) {
    // process s, including s == 0
    if (s == 0) break;
}

This form also handles m == 0: the body runs once for the empty submask. By contrast, the non-empty loop runs zero times when m == 0.

Complexity and the 3^n Pattern

If m contains $k = \operatorname{popcount}(m)$ set bits, each of those bits is either present or absent in s. There are exactly $2^k$ submasks, so direct submask enumeration takes $O(2^k)$ time and $O(1)$ extra space. The complexity depends on the number of set bits in m, not on the machine word size.

A common bitmask DP nests this loop inside an outer loop over every $n$-bit mask:

for (uint32_t m = 0; m < (1u << n); ++m) {
    for (uint32_t s = m; ; s = (s - 1) & m) {
        // process the pair (s, m), where s is a submask of m
        if (s == 0) break;
    }
}

Across all outer masks, each bit has three legal states: outside m, inside m but outside s, or inside both m and s. The forbidden fourth state, inside s but outside m, would violate $s \subseteq m$. Three choices for each of $n$ bits give $3^n$ valid pairs. The same result follows from the binomial theorem:

$$\sum_{m=0}^{2^n - 1} 2^{\mathrm{popcount}(m)} = \sum_{k=0}^{n} \binom{n}{k} 2^k = 3^n,$$

Thus, iterating every mask and every one of its submasks costs $O(3^n)$ rather than $O(4^n)$. Typical uses include partition DP, choosing a feasible group from currently available elements, and transitions that split m into s and m ^ s.

Common Mistakes

• Using only s--: the loop visits integers containing bits outside m, so most values are not submasks.
• Forgetting the empty mask: while (s) and s != 0 intentionally exclude it. DP base cases often require the explicit-break form.
• Missing the zero break: a loop that processes zero and then continues can wrap back to m and run forever.
• Confusing submasks with set bits: clearing the lowest bit with x &= x - 1 visits one set bit at a time; (s - 1) & m visits every combination of the allowed bits.

GCC Bit Builtins

__builtin_popcount(m)    // number of set bits (popcount uses popcnt instr.)
__builtin_popcountll(m)  // 64-bit version
__builtin_ctz(m)         // index of lowest set bit (count trailing zeros) — UB if m == 0
__builtin_clz(m)         // count leading zeros — UB if m == 0
__builtin_parity(m)      // popcount(m) & 1

// Iterate set bits cheaply (low-bit-first):
for (int x = m; x; x &= x - 1) {
    int bit = __builtin_ctz(x);   // position of lowest set bit
    // use bit
}

C++20 adds portable equivalents in <bit>: std::popcount, std::countr_zero, std::countl_zero, std::has_single_bit.

std::bitset for Fixed-N Boolean Arrays

For a set drawn from a fixed universe of size $N$ known at compile time, std::bitset<N> is dramatically faster than std::vector<bool>: it packs 64 bits per word, supports word-parallel &, |, ^, <<, >>, and gives an effective $O(N/64)$ speedup.

#include <bitset>
std::bitset<1000> a, b;
a.set(5); a.set(42);
auto c = a & b;            // word-parallel intersection
size_t k = a.count();      // popcount
bool any = a.any();        // is any bit set?
size_t lo = a._Find_first();           // GCC extension: lowest set bit
size_t nx = a._Find_next(lo);          // next set bit after lo
a <<= 3;                   // shift entire bitset

Classic CP applications: subset-sum / knapsack reachability (dp |= dp << w[i]), graph reachability via boolean matrix multiplication, and string matching (Shift-Or).

Summary

• A bit mask selects specific bits from a value using AND, OR, XOR.
• Create masks with shifts: 1u << i for single bit, ((1u << n) - 1) for lower n bits.
• Extract fields: shift then mask. Set fields: clear then OR.
• Masks are used everywhere: file permissions, feature flags, network masks, set operations.
• An integer represents a subset: OR = union, AND = intersection, XOR = symmetric difference.

Practice Problems

• LC 78. Subsets Easy — enumerate every subset of an array using a bitmask from 0 to 2^n - 1.
• LC 90. Subsets II Medium — sort and skip duplicate masks; classic mask + dedup.
• LC 1239. Maximum Length of a Concatenated String with Unique Characters Medium — represent each word as a 26-bit mask; combine subsets where AND is 0.
• LC 526. Beautiful Arrangement Medium — permutation counting via bitmask DP, $O(n \cdot 2^n)$.
• LC 1255. Maximum Score Words Formed by Letters Hard — iterate all subsets of the word set; check letter budget per mask.
• LC 1494. Parallel Courses II Hard — DP over taken-courses mask; iterate subsets of "available" using s = (s-1) & m.
• LC 943. Find the Shortest Superstring Hard — TSP-style bitmask DP: dp[mask][last].
• CSES — Hamming Distance CSES — compare 30-bit masks pairwise; __builtin_popcount(a ^ b).