cf.completefrontend
BIT MANIPULATION · FOUNDATION

Bit flags

Store many on/off options in one number, one bit per option, and grant, revoke, toggle, or check them with single bitwise operations.

Time O(1)Space O(1)7 practice problemsStep-through picture

The idea

A bit flag gives each option its own bit: READ is bit 0 (value 1), WRITE is bit 1 (value 2), DELETE is bit 2 (value 4), and so on. A set of options is then one number that adds up the bits that are on: read plus write is 1 | 2 = 3.

Every operation is one bitwise step. Grant a flag with mask | flag. Revoke it with mask & ~flag. Toggle it with mask ^ flag. Check that all of some flags are on with (mask & flags) === flags, or that any of them is on with (mask & flags) !== 0.

This is compact (up to 31 options in one number in JavaScript), fast, and easy to compare or store. Browsers, graphics APIs, compilers, and React itself use flags this way.

An everyday example

A key ring with labeled hooks

A key ring has labeled hooks: hook 0 is the front door, hook 1 the garage, hook 2 the office, hook 3 the mailbox. Looking at the ring, you can see which keys someone holds. Handing over a key fills a hook, taking it back empties it, and asking "can they open the garage and the office?" means checking two hooks at once.

How the example maps to the code
In the exampleIn the code
A hook with its labelPermission.WRITE, which is 1 << 1
The whole key ringmask
Handing over a keygrant(mask, flag), which is mask | flag
Taking a key backrevoke(mask, flag), which is mask & ~flag
Checking for several keys at once(mask & flags) === flags

From the slow way to bit flags

  1. Start with the obvious way to store permissions: an object of booleans, like { read: true, write: false, delete: true, share: false }. It's readable, but checking "has read and delete" needs two lookups, comparing two permission sets needs a loop over the keys, and storing it in a URL or a database takes a lot more space than a number.
  2. Give each option its own bit instead: READ is 1, WRITE is 2, DELETE is 4, SHARE is 8. Each value is a power of two, so each has a single 1 bit in its own position. A set of options becomes one number whose bits say which options are on: read plus delete is 0101, which is 5.
  3. Now every set operation is one operator. Adding options is OR, removing them is AND with the flipped flags, and toggling is XOR. Because the operators work on all bits at once, you can grant or check several flags in one step, such as READ | DELETE.
  4. Checking needs one more idea: mask & flags keeps only the asked-about bits that are on. If that equals flags, all of them are on; if it's not 0, at least one is. Name the powers of two in one object and wrap each operation in a tiny function. Those functions are bit flags.

How it works

  1. Give each option its own power of two: 1 << 0, 1 << 1, 1 << 2, and so on.
  2. Combine options with |: Permission.READ | Permission.WRITE is 3.
  3. Grant with mask | flag, revoke with mask & ~flag, and toggle with mask ^ flag.
  4. Check that every flag in flags is on with (mask & flags) === flags.
  5. Check that at least one is on with (mask & flags) !== 0.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. const Permission = {
  2. READ: 1 << 0,
  3. WRITE: 1 << 1,
  4. DELETE: 1 << 2,
  5. SHARE: 1 << 3,
  6. };
  8. function grant(mask, flag) {
  9. return mask | flag;
  10. }
  12. function revoke(mask, flag) {
  13. return mask & ~flag;
  14. }
  16. function toggle(mask, flag) {
  17. return mask ^ flag;
  18. }
  20. function hasAll(mask, flags) {
  21. return (mask & flags) === flags;
  22. }
  24. function hasAny(mask, flags) {
  25. return (mask & flags) !== 0;
  26. }

How fast it is

TimeO(1)
Extra memoryO(1)

Each operation is one bitwise step on one number, however many flags are combined.

  • Best caseO(1)

    Any call: one bitwise operation, and a comparison for the checks.

  • Average caseO(1)

    The same single step whether flags names one option or ten.

  • Worst caseO(1)

    Still one step with all 31 safe flags combined. An object of booleans would need one lookup per flag instead.

Common mistakes

  • Numbering flags 1, 2, 3, 4 instead of 1, 2, 4, 8. Then 3 is both a flag and 1 | 2, and checks give wrong answers.
  • Checking several flags with mask & flags as a boolean. That is true if any of them is on; use === flags when all must be on.
  • Revoking with mask ^ flag. If the flag was off, XOR turns it on. Use mask & ~flag.
  • Defining more than 31 flags. 1 << 31 is negative and 1 << 32 wraps around to 1.

When to use it

Look for these clues in a problem:

  • The problem has a fixed, small set of yes/no options: permissions, features, modifier keys, states.
  • Options are combined, compared, or stored and sent as one value.
  • You need fast checks like "has all of these" or "has any of these".
  • The statement uses words like flags, mask, lanes, or bit field.

Check yourself

Answer each one in your head first, then open it.

Why must every flag be a power of two?

So each has one 1 bit in its own position. If flags were 1, 2, 3, then 3 would look exactly like 1 | 2, and you couldn't tell them apart.

What does revoke(13, WRITE) return, and what would 13 ^ WRITE give?

revoke returns 13, because WRITE was already off. 13 ^ 2 gives 15, turning WRITE on by mistake.

Why does hasAll compare with === flags instead of just checking mask & flags?

mask & flags is non-zero when any of the flags is on. Only when it equals flags are all of them on: 5 & 3 is 1, not 0, yet WRITE is off.

What does hasAll(5, 0) return?

true, because 5 & 0 is 0, which equals the flags value 0. Checking an empty list of flags always passes.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Each flag is a different power of two, so each has exactly one 1 bit, and no two share a position. ORing flags together never carries from one position to another, so the resulting mask has a 1 exactly at the positions of the chosen flags. Different sets of flags always give different numbers, and every flag can be read back.

Each operation changes only the positions named in flag. OR with 0 keeps a bit and OR with 1 sets it, so grant turns on the flag bits and leaves others alone. ~flag has 0 at the flag positions and 1 elsewhere, so revoke clears exactly those positions. XOR with 1 flips and XOR with 0 keeps, so toggle flips exactly those positions.

mask & flags keeps a bit only where both have a 1, so it's the set of asked-for flags that are actually on. If every asked-for flag is on, that's all of flags, which is what hasAll compares with. If any is on, the result has at least one 1 bit and isn't 0, which is what hasAny checks.

Going deeper

3 more ideas

Why each flag needs its own bit

If two options shared a bit, turning one on would look the same as turning the other on. Powers of two each have a single 1 bit in a different place, so any combination of them gives a unique number, and every option can be read back with &.

How React uses flags and lanes

Inside React, each fiber (the object React keeps for every rendered component) has a flags field: a bit field saying what work it needs, such as placement or update. React also tracks update priorities as lanes, which are bits in a 31-bit number. Pending work is the OR of lanes, and a lower bit means a higher priority, so React can pick the most urgent lane with lanes & -lanes, which keeps only the lowest set bit.

Limits and alternatives

JavaScript's bitwise operators use 32-bit signed integers, so at most 31 flags are safe if you want to avoid the sign bit. For more, use several numbers, a BigInt, or a Set of names. A Set is easier to read, so use flags when you need compact storage, fast combining, or an API that expects them.

Work it by hand

Every step in a table, with why

Change one permission mask through a series of calls, including two that change nothing, and check it four ways.

mask = 0, with READ = 1, WRITE = 2, DELETE = 4, SHARE = 8

StepCallmaskBits (SDWR)What happensWhy
1start00000no permissionsThe bits are written as SHARE, DELETE, WRITE, READ from left to right.
2grant(mask, SHARE)810000 | 8OR turns on bit 3 and leaves the rest alone.
3grant(mask, DELETE | READ)1311018 | 5DELETE | READ is 0101, so one call grants two flags.
4grant(mask, READ)131101already on: no changeOR with a bit that's already 1 keeps it 1. Granting twice is safe.
5revoke(mask, WRITE)131101already off: no change~2 is all ones except bit 1, so AND keeps WRITE off. toggle here would have turned it on, giving 15.
6toggle(mask, SHARE)5010113 ^ 8XOR flips bit 3 from on to off.
7hasAll(mask, READ | DELETE)50101true5 & 5 is 5, which equals the flags asked for: both are on.
8hasAll(mask, READ | WRITE)50101false5 & 3 is 1: READ is on but WRITE isn't, so the result isn't 3.
9hasAny(mask, WRITE | SHARE)50101false5 & 10 is 0: neither flag is on.
10hasAny(mask, READ | SHARE)50101true5 & 9 is 1, which isn't 0: at least one of them, READ, is on.
11revoke(mask, READ | DELETE)000005 & ~5Revoking both remaining flags at once leaves no permissions.

The mask ends at 0. Each call was one bitwise operation on one number, however many flags it touched, and granting an on flag or revoking an off flag changed nothing.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bit flagsO(1)O(1)Up to 31 fixed options that you combine, compare, or store often: permissions, render state, feature switches.
Object of booleansO(k)O(k)A few options where readable code and JSON matter more than speed; checking k flags takes k lookups.
Set of namesO(k)O(k)Options that change at runtime or number more than 31.

Extra memory: O(1): one number holds up to 31 flags, 4 bytes of information.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Bit flags and the other approaches, on a scale where each line up is 10 times more steps.
  • Bit flags O(1)
  • Object of booleans, Set of names O(k)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Bit flags111
Object of booleans101,0001 million
Set of names101,0001 million

Inputs that need care

5 tricky inputs
Checking no flags: hasAll(mask, 0) and hasAny(mask, 0)
hasAll is always true (every flag in an empty list is on) and hasAny is always false. If flags is built from user input, decide what an empty request should mean.
A misspelled flag: Permission.EDIT, which is undefined
grant(5, undefined) returns 5 without any error, because undefined becomes 0. hasAll(5, undefined) is false. Define flags in a frozen object or a TypeScript enum so typos fail loudly.
Revoking a flag that is already off: revoke(13, WRITE)
Returns 13, unchanged. Using 13 ^ WRITE instead would wrongly turn WRITE on, giving 15.
A 32nd flag: 1 << 31 and 1 << 32
1 << 31 is negative, so tests like mask > 0 break; 1 << 32 wraps to 1 and collides with READ. Stop at 31 flags, or switch to BigInt or several numbers.
Stored masks after the flags change
A mask saved as 13 means "SHARE, DELETE, READ" only while those bit positions keep their meaning. Never renumber existing flags; only add new ones in new positions.

Variations and follow-ups

Twists interviewers add

Named combinations

Define common groups as flags too: EDITOR = READ | WRITE is 3, and ADMIN = READ | WRITE | DELETE | SHARE is 15. hasAll(mask, EDITOR) then checks a whole role in one step.

Priorities as bits

React keeps pending update priorities as bits called lanes, where a lower bit means more urgent. The most urgent pending one is the lowest set bit, lanes & -lanes, found in one step without a loop.

Listing and counting flags

To show a mask to a person, loop over the flag object and keep the names where hasAll(mask, value) is true. To know how many flags are on, count its 1 bits.

A Set of names

new Set(["read", "delete"]) is easier to read and has no 31-item limit. It's the better choice when compact storage and one-step checks don't matter.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "permissions", "feature switches", "a set of states that can combine", "store several booleans compactly", or an API that takes options like READ | WRITE.
  • Explain the encoding first: "each option is a power of two, so it has its own bit". Then each operation is one line: OR to grant, AND NOT to revoke, XOR to toggle, AND then compare to check.
  • Test granting a flag that's already on, revoking one that's already off, and checking several flags at once, both all and any. These show why revoke can't use XOR and why hasAll needs === flags.
  • Expect "what if we need 40 flags?". Answer: JavaScript's bitwise operators are 32-bit, so use BigInt, two numbers, or a Set, and explain the trade-off in readability.

Where frontend code uses it

The same idea in real UI code
  • React stores each fiber's pending work in a flags bit field and update priorities as lanes, which are bits where a lower bit means a more urgent update.
  • MouseEvent.buttons is a bit field: 1 is the primary button, 2 the secondary, 4 the middle, so (event.buttons & 2) !== 0 checks the right button.
  • document.createTreeWalker(root, NodeFilter.SHOW_ELEMENT | NodeFilter.SHOW_TEXT) picks which node types to visit with flags.
  • The TypeScript compiler marks types and symbols with flag enums such as TypeFlags, checked with &.

Related algorithms