What Is a Set Bit? The Building Block Behind Every Bitmask

You're staring at (n >> k) & 1. Your interviewer wrote it, looked pleased with themselves, and moved on. You nodded like you understood. You didn't.

That's fixable. Right now.

A set bit is a 1 at a specific position in a binary integer. A mask is the integer you construct to reach in and inspect or flip that position. Every "clever" bit trick you've ever seen is just those two ideas recombined in slightly different orders. Once they click, you'll be the one writing (n >> k) & 1 and looking smug about it.

What a Set Bit Actually Means

A bit is "set" when its value is 1, and "unset" (or "cleared") when its value is 0. The terminology comes from hardware: you set a flag to record something true, you clear it to say it's false. Software engineers just kept the vocabulary.

Take the number 13. In binary, that's 1101. Reading right to left from position 0:

Position:  3  2  1  0
Bits:      1  1  0  1

Positions 0, 2, and 3 are set. Position 1 is not. "The number of set bits in 13 is 3" means exactly that: count the 1s.

This is what popcount and Python's bit_count() measure. It's also what LeetCode 191 (Number of 1 Bits) tests, in case you want to meet this idea in a controlled environment before it ambushes you.

What Is a Mask?

A mask is an ordinary integer whose bit pattern you've chosen deliberately, so you can use it to inspect or modify another integer.

The name comes from masking tape. Cover the bits you don't care about. Expose only what you want. Unlike masking tape, it doesn't leave residue on the wall.

The most common mask: a single 1 at position k, 0s everywhere else. You build it with a left shift:

mask = 1 << k

For k = 2, that gives 0b100, which is 4. The 1 sits at position 2. Simple, but this one construct is the entire construction kit for everything below.

Four Operations, Every Interview

Every bit manipulation problem bottoms out in one of these four patterns. Memorize them by what they do, not by the angle-bracket soup.

Check Whether Bit k Is Set

is_set = (n >> k) & 1

Shift n right by k so the target bit drops to position 0. AND with 1. Get back 1 if set, 0 if not.

You can also write bool(n & (1 << k)). Both are equivalent. The first is cleaner when you need a 0/1 integer; the second makes the mask explicit for whoever is reading this at 2 a.m. trying to understand your code.

Set Bit k (Force It to 1)

n = n | (1 << k)

OR never turns a 1 into 0. So all other bits stay put while position k becomes 1 regardless of what was there before.

Clear Bit k (Force It to 0)

n = n & ~(1 << k)

~(1 << k) flips the mask, putting 1s everywhere except position k. AND forces that position to 0 while leaving everything else alone.

Toggle Bit k (Flip It)

n = n ^ (1 << k)

XOR with 1 flips. XOR with 0 does nothing. Every other position sees XOR with 0, so they stay put.

These four patterns are the entire alphabet of bit manipulation. Everything else is a sentence made from them.

A meme about checking if n is even with n & 1 vs n % 2

When your interviewer asks for "the most efficient" even-number check and your hand moves toward n & 1 before you've finished thinking

Working Through an Example

n = 0b1010 (decimal 10). Target: bit position 1.

n =  1 0 1 0
pos: 3 2 1 0

Bit 1 is currently 1 (set).

k = 1
mask = 1 << 1   # 0b0010

# Check
(n >> 1) & 1    # 0b0101 & 1 = 1  (it's set)

# Clear it
n & ~mask       # 0b1010 & 0b1101 = 0b1000 = 8

# Toggle it (flips 1 to 0)
n ^ mask        # 0b1010 ^ 0b0010 = 0b1000 = 8

Now reverse it: pretend bit 1 starts as 0, making n = 0b1000 (8). Check returns 0. Toggle gives 0b1000 ^ 0b0010 = 0b1010 = 10. Set gives the same 10, because OR never clears. You can trace either direction in your head with just the four rules.

When One Bit Isn't Enough

Masks don't have to isolate a single position. OR several single-bit masks together to select multiple positions at once:

# Select bits 0, 2, and 3
mask = (1 << 0) | (1 << 2) | (1 << 3)  # 0b1101 = 13

AND-ing n with this preserves those bits and zeros the rest. OR-ing sets all of them at once. This comes up in bitmask DP whenever you're building or testing subsets.

The other essential shape: a mask for the lowest k bits.

mask = (1 << k) - 1

For k = 4: 1 << 4 = 0b10000. Subtract 1: 0b01111. AND with this extracts the bottom 4 bits. Useful for isolating nibbles, extracting packed fields, or doing modular arithmetic on partial words.

The Trick That Appears Everywhere: `n & (n - 1)`

This one looks like someone sneezed on a keyboard and checked it in.

n & (n - 1) clears the lowest set bit of n. Why? Subtracting 1 flips the lowest set bit to 0 and turns everything below it to 1. AND-ing with the original zeros out all those positions.

n     = 1 0 1 1 0 0  (44)
n - 1 = 1 0 1 0 1 1  (43)
AND   = 1 0 1 0 0 0  (40)

Two uses you'll see constantly: count set bits in O(popcount) iterations instead of O(word size), and check whether n is a power of two (n > 0 && n & (n - 1) == 0 means exactly one bit is set, period).

The inverse, n & -n, isolates the lowest set bit. Two's complement negation flips all bits and adds 1, which clears everything below the lowest set bit. AND keeps only the shared position. Between the two, you can extract or strip individual set bits in a loop.

99 in binary is 1100011, a riff on Jay-Z's 99 Problems

99 in binary is 1100011. Jay-Z had 1100011 problems. This has been your bit representation check for the day.

A Gotcha Worth Knowing

In C++ and Java, ~ on a 32-bit signed integer flips all 32 bits including the sign bit. ~0 == -1 in two's complement. That's correct and expected.

In Python, integers have arbitrary precision, so ~n == -(n + 1) always. ~0 == -1 as well. If you're computing a mask in Python and expecting a positive 32-bit result, AND with 0xFFFFFFFF to extract the 32-bit interpretation. Otherwise you'll stare at a negative number for five minutes and wonder if you've been writing wrong Python your entire career. (You haven't. Python is just built different.)

O(1) Space for a Boolean Array

Bitwise operations are O(1) on standard 32- or 64-bit integers. No loops. No allocation.

The space payoff is the reason bitmasks matter in DP. An array of n booleans costs O(n) space. An integer with n bits costs O(1). For n up to 64, the entire boolean array fits in a single machine word.

This is why bitmask DP can represent an exponential state space without exponential memory overhead. Each of the 2^n subsets encodes as an integer. Checking or setting membership is O(1). No hash set, no allocation per state.

For Held-Karp (Traveling Salesman DP), each state is (current_city, visited_set) where visited_set is a bitmask. State space is O(n · 2^n), time is O(n² · 2^n). That wouldn't be tractable if each subset were an actual set object with heap allocation and pointer chasing.

When a problem gives you 1 <= n <= 20, that's a bitmask hint. 2^20 is about a million, fine. 2^30 isn't. The constraint is telling you the expected complexity.

Where This Shows Up in Interviews

Bit manipulation problems cluster into a few recognizable shapes:

Subset enumeration. Iterate mask from 0 to 2^n - 1. Bit k of mask tells you whether element k is included. See bitmask subset enumeration for the full pattern.

State compression in DP. Encode "which items have I visited" as a bitmask. Transitions check and set bits. Bitmask DP covers this in depth.

Duplicate detection. XOR all elements. Pairs cancel, leaving only the number appearing an odd number of times. The XOR trick is just repeated toggling.

Efficient popcount. Integer.bitCount(n) in Java, bin(n).count('1') in Python, __builtin_popcount(n) in C++ are all O(1) for 32-bit integers. Knowing these saves you from reinventing the wheel on camera, in front of someone who's seen the wheel get reinvented badly three times today already.

The weak spot for most candidates isn't writing the code. It's explaining it out loud. A voice-based mock interview at SpaceComplexity forces you to say "I'm using a mask with a 1 at position k and AND-ing to check if that bit is set" rather than just typing (n >> k) & 1 in silence. That narration is what earns the point in a real interview.

The Short Version

A set bit is 1 at a position. An unset bit is 0.
A mask is an integer whose bit pattern you choose deliberately to check, set, clear, or toggle specific bits in another integer.
Four operations: check with (n >> k) & 1; set with |; clear with & ~mask; toggle with ^.
n & (n - 1) clears the lowest set bit. n & -n isolates it.
(1 << k) - 1 builds a mask for the lowest k bits.
Bitmasks give you O(1) space for a boolean array of up to 64 elements and are the backbone of subset enumeration and bitmask DP.
n <= 20 in the constraints is almost always a bitmask hint.