skip to content

Bitmasks as Sets & State

27 roadmaps5 questions

Learn to pack a whole set into a single integer — one bit per element — and manipulate it with O(1) operations. Interviewers ask this because bitmask state encoding powers subset enumeration, visited-set tracking, and permission flags, and shows you can trade readability for compact, fast state.

part ofData structures & algorithmsoverview, primer and where to startread it →
on this pageshow

explore

questions

5

In a permission bitmask, how do you grant, revoke and test one flag without disturbing the others?

level: juniorimportance: must knowfreq 68%

answer

  1. three operations, three different operators
  2. one turns bits on, one turns them off
  3. the clear operator needs a complement
  4. toggling is not the same as clearing
  5. any-of versus all-of changes the comparison

basics

~20 s

Grant with OR: mask | FLAG. Revoke by ANDing the complement: mask & ~FLAG. Test membership with (mask & FLAG) != 0. XOR toggles rather than clears, so it is the wrong operator for revoke.

solid answer

~50 s

A flag constant is a single set bit, so the whole set of permissions lives in one integer. Grant is `mask = mask | FLAG` — OR only ever turns bits on, so every other permission survives. Revoke is `mask = mask & ~FLAG`: the complement has zeros only where FLAG has ones, so exactly that bit is cleared and everything else passes through untouched. Membership is `(mask & FLAG) != 0`, not `mask == FLAG` — the AND yields FLAG's own value when present and zero when absent, and equality against FLAG only works if no other permission is held. For multi-bit checks the two questions differ: `(mask & NEEDED) != 0` means holds any of them, `(mask & NEEDED) == NEEDED` means holds all of them. XOR flips a bit, so using it to revoke silently grants the permission when the holder did not already have it.

go deeper

for a junior

Be ready to write the three one-line operations from memory and say what each one does to the bits you are not touching. Knowing that OR sets, AND-with-complement clears, and XOR toggles is the whole answer at this level.

for a middle

Explain why a flag constant is a single set bit and why the membership test compares against zero rather than one. Be able to build both the any-of and the all-of test over a multi-bit requirement and say how they differ.

for a senior

Show the operational judgment: a revoke written with the toggling operator is a privilege-escalation bug that single-flag tests will not catch, and bit positions become a frozen contract the moment a mask is persisted or sent to a client.

for a principal

Own the boundary. Decide whether raw masks ever escape the module that owns the constants, insist that mutation goes through one small audited helper instead of hand-written bit twiddling at call sites, and set the policy for retiring flag positions.

## The representation A bitmask stores a set of up to w members in a single w-bit integer. Each member is assigned a fixed bit position, and its constant is that position's value: member 0 is `1 << 0` = 1, member 1 is `1 << 1` = 2, member 2 is `1 << 2` = 4, and so on. A permission set is then the bitwise OR of the constants it contains — `READ | WRITE | DEPLOY` might be `1 | 2 | 8` = 11, binary `1011`. Nothing else is stored: the number *is* the set. That identity is what makes the three basic operations one machine instruction each, and it is why the operators must be chosen for what they do to the bits you are *not* touching. ## Grant — OR `mask = mask | FLAG` OR produces a 1 wherever either side has a 1. Bits outside FLAG see `bit | 0`, which leaves them exactly as they were; the FLAG bit becomes 1 whether it was 0 or 1. Granting is therefore idempotent: granting a permission twice is the same as granting it once. Granting several at once is one operation — `mask | (READ | WRITE)`. The classic beginner error here is assignment instead of OR: `mask = FLAG` replaces the whole set with a single permission and quietly deletes everything else. ## Revoke — AND with the complement `mask = mask & ~FLAG` `~FLAG` (bitwise NOT) is all ones except a zero at FLAG's position. ANDing with it passes every other bit through unchanged (`bit & 1` = `bit`) and forces FLAG's bit to 0 (`bit & 0` = 0). Like grant, this is idempotent: revoking something the holder never had is a no-op. Revoking a group is `mask & ~(A | B)`. ## Why XOR is not revoke XOR yields 1 when exactly one side has a 1, so `mask ^ FLAG` *toggles*: on becomes off, and off becomes **on**. It looks correct in a test that first grants and then revokes, because toggling a set bit does clear it. It is wrong the moment revoke is called on a holder who does not have the permission — the operation grants it. In an access-control service that is a privilege-escalation bug produced by an operation named "remove", and it usually survives review because the happy-path test passes. XOR is the right operator only when you genuinely want a toggle, such as flipping a feature switch. ## Testing — compare against zero, or against the whole requirement `(mask & FLAG) != 0` AND keeps a bit only if both sides have it, so `mask & FLAG` is either FLAG's value or zero. Two errors are common. The first is `mask == FLAG`, which asks "is this the *only* permission held" and fails as soon as a second one is granted. The second is `(mask & FLAG) == 1`, which is true only for the lowest bit, because a set flag evaluates to its own value (8, 1024, …) rather than to 1. With a multi-bit requirement the test must say which question you are asking: | Intent | Expression | |---|---| | holds at least one of them | `(mask & NEEDED) != 0` | | holds all of them | `(mask & NEEDED) == NEEDED` | | holds none of them | `(mask & NEEDED) == 0` | | holds only these | `(mask & ~NEEDED) == 0` | Confusing the first two is the second-most-common bug in flag code after XOR-as-revoke, and it also fails safe-looking review: with a single-bit NEEDED the two expressions agree, so the difference only shows up once someone passes a union. ## Set algebra comes for free Because the mask is a set, role composition is arithmetic on words: the union of two roles is `roleA | roleB`, the permissions two roles share is `roleA & roleB`, what one role has that another lacks is `roleA & ~roleB`, and "is role A entirely contained in role B" is `(roleA & roleB) == roleA`. Each is a constant-time whole-set operation regardless of how many permissions are involved, which is the real reason services reach for masks on hot authorization paths. ## Operational care Bit positions are a permanent contract once a mask has been persisted or sent anywhere. Inserting a new permission in the middle of the constant list renumbers everything after it and silently reinterprets every stored value, so new flags are always appended at the next free position and retired ones leave a hole rather than being reused. Keep the constants and the grant/revoke/test helpers in one small module: hand-written bit twiddling scattered across call sites is where the toggle-instead-of-clear bug is born.

  • How would you revoke several permissions in a single operation?
    Build the union first, complement it once, and AND: `mask = mask & ~(DEPLOY | AUDIT)`. The complement has zeros exactly at those two positions, so both are cleared and every other permission passes through. Revoking flags one at a time in a loop is correct too, just needlessly repeated work on a hot path.
  • Why is the membership test written against zero rather than against one?
    A flag constant is `1 << k`, so ANDing it out yields its own value — 1024 for bit 10, not 1. Comparing to 1 is true only for the lowest bit and silently false for every other permission. Comparing against zero works for any position, and comparing against the flag itself works for a multi-bit requirement.
  • A teammate inserts a new permission constant in the middle of the list so it reads alphabetically. What breaks?
    Every constant after it shifts up one bit position, so every mask already stored or already sent to a client now decodes to different permissions — a stored 12 that meant AUDIT plus DEPLOY may now read as DEPLOY plus something nobody granted. Bit positions are a wire and storage contract: append new flags at the next free bit and never reuse a retired one.

Think of a row of light switches on one panel. OR flips the chosen switch up, AND with the complement flips it down, and XOR just flips whatever it finds — which is fine for a toggle and dangerous for an operation called revoke.

saying these in an interview costs you the question

  • Revokes with XOR, which grants the flag when it was absent
  • Tests with mask equals FLAG, which fails once a second flag is set
  • Assigns mask = FLAG to grant, wiping every other permission
  • Uses a non-zero AND result to mean the holder has all requested flags
  • Reuses a retired bit position for a new permission
  • Treats the logical and bitwise operators as interchangeable

context

resolving links…

open as a page

Why does counting an integer from 0 to 2^n - 1 enumerate every subset of an n-element set?

level: middleimportance: must knowfreq 58%

basics

~20 s

Every n-bit integer is a distinct in-or-out choice for each of the n elements, and counting from 0 to 2^n - 1 visits every n-bit pattern exactly once. The number itself is the subset; no list is built.

open as a page

Your permissions service outgrows 31 flags in a 32-bit mask — what breaks, and how do you fix it?

level: seniorimportance: should knowfreq 32%

basics

~20 s

Flag 31 lands on the sign bit, so masks turn negative. Past that, shifting by 32 or more is not a reliable zero: many environments reduce the count modulo the width, so flag 32 silently aliases flag 0.

open as a page

When is a bitmask the wrong representation for a permission model your team must maintain for years?

level: principalimportance: should knowfreq 30%

basics

~20 s

A mask wins when the check path is hot and the flag list is stable; it loses when permissions must be read by humans, grow steadily, or are persisted — positions freeze into a contract and capacity is capped.

open as a page

In submask enumeration, why does s = (s - 1) & m walk exactly the subsets of mask m?

level: middleimportance: nice to knowfreq 18%

basics

~20 s

Subtracting one borrows through the lowest set bit, clearing it and setting all bits below; ANDing with m discards bits m does not own. The result is the next-smaller submask, so the loop descends through all of them.

open as a page