Bit manipulation looks intimidating at first. Shifting bits, flipping 1s and 0s, and reading expressions like n & (n - 1) takes practice to parse.

Bit manipulation is a common topic in coding interviews. A handful of techniques can solve a wide range of problems, often in O(1) space and with very fast performance.

Computers store and process data as bits. Operating on bits directly often leads to shorter, faster solutions than working at the decimal level.

In this chapter, we will cover:

Bit manipulation is the process of performing operations directly on the binary representation of numbers. Instead of working with decimal values, you work with individual bits (0s and 1s).

Every integer in a computer is stored as a sequence of bits. For example, 5 in binary is 101. In an actual int (typically 32 bits in Java/C#), it's stored as 00000000 00000000 00000000 00000101 with leading zeros. We'll often show just the relevant low bits for clarity.

Why Learn Bit Manipulation?

First, here are the six fundamental bitwise operators.

1. AND (&)

Returns 1 only if both bits are 1.

Use case: Check if a specific bit is set, clear bits, extract bits.

2. OR (|)

Returns 1 if at least one bit is 1.

Use case: Set specific bits to 1.

3. XOR (^)

Returns 1 if the bits are different.

Use case: Toggle bits, find unique elements, swap values.

Key property: a ^ a = 0 and a ^ 0 = a

XOR Swap (Without a Temp Variable)

XOR can swap two variables in place:

This is mostly a trivia question. Modern compilers generate the same code for temp = a; a = b; b = temp;, and the XOR version breaks when a and b alias the same memory location (both end up as 0). Use the temp version in real code.

Parity and Single-Number Tricks

x & 1 is 1 if x is odd and 0 if x is even. It is cheaper than x % 2 and avoids the sign-handling pitfalls of modulo on negative numbers.

XOR of an entire array equals the XOR of bits across all positions. This is the trick behind LC 136 (Single Number): if every element appears twice except one, XOR-ing them all cancels the pairs because a ^ a = 0, leaving only the unique element.

4. NOT (~)

Flips all bits (0 becomes 1, 1 becomes 0).

Note: In most languages, ~n = -(n + 1) due to two's complement representation.

5. Left Shift (<<)

Shifts bits to the left by specified positions. Each shift multiplies by 2.

Formula: n << k = n × 2^k

This holds as long as the result fits in the integer type's range. In Java, 1 << 31 produces Integer.MIN_VALUE (the sign bit is set), not 2^31. Use 1L << 31 to stay in the positive range.

6. Right Shift (>>)

Shifts bits to the right by specified positions. Each shift divides by 2 (integer division).

For non-negative n, n >> k equals n / 2^k. For negatives in Java/C++ arithmetic shift, the result is floored, not truncated: -1 >> 1 is -1, while -1 / 2 is 0.

Arithmetic vs Logical Right Shift

Java and JavaScript distinguish two right-shift operators:

C++, C#, Go, Python, Rust use a single >> operator with language-specific sign-handling rules. In C++, behavior of >> on signed negatives was implementation-defined until C++20; from C++20 onward it's arithmetic shift.

These techniques appear repeatedly in coding interviews.

1. Check if a Bit is Set

To check if the k-th bit (0-indexed from right) is set to 1:

How it works:

2. Set a Bit

To set the k-th bit to 1:

How it works: OR with a mask that has 1 at position k.

3. Clear a Bit

To clear (unset) the k-th bit:

How it works: AND with a mask that has 0 at position k and 1s everywhere else.

4. Toggle a Bit

To flip a bit (0 to 1, or 1 to 0):

How it works: XOR with a mask that has 1 at position k.

5. Check if Power of 2

A number is a power of 2 if it has exactly one bit set.

How it works:

6. Count Set Bits (Brian Kernighan's Algorithm)

Count the number of 1s in the binary representation:

Why it works: n & (n - 1) clears the rightmost set bit. We count how many times we can do this before n becomes 0.

Time complexity: O(number of set bits), not O(32)

Built-in Bit Counting Primitives

Every modern language ships with built-in bit counting functions. They are usually faster than hand-written code (often compiling to a single CPU instruction like POPCNT) and clearer to read.

Use the built-in for production code. The Brian Kernighan trick is still worth knowing for interviews when the question is "implement popcount from scratch."

7. Get the Rightmost Set Bit

Extract the rightmost bit that is set to 1:

How it works: In two's complement, -n = ~n + 1. This creates a number where only the rightmost set bit survives the AND.

Note: for n = Integer.MIN_VALUE in Java, -n overflows back to Integer.MIN_VALUE. The trick happens to work correctly here (the result is Integer.MIN_VALUE itself, which has only the highest bit set), but the overflow is worth understanding.

8. Turn Off the Rightmost Set Bit

This is the same trick used in counting set bits and checking power of 2.

A 32-bit integer can encode any subset of a 32-element set: bit i is 1 if element i is in the subset, 0 otherwise. For small universes (up to about 20 elements), a single integer used as a bitmask is much faster than a HashSet<Integer> because subset operations become single bitwise instructions.

Core Operations on a Mask

For a mask representing a subset:

To iterate over every element in the mask:

Enumerating Subsets of a Mask

Sometimes a problem asks you to enumerate every subset of a given set. The standard trick:

This iterates exactly 2^popcount(mask) subsets. Summing across all 2^n possible masks gives O(3^n) total iterations, which is a classic complexity bound for bitmask DP that enumerates subsets of subsets.

Bitmask DP

Bitmask DP uses a mask as part of the DP state. Three common examples:

Traveling Salesman Problem. dp[mask][i] is the shortest path that visits exactly the cities in mask and ends at city i. Transitions add one city at a time. Complexity: O(n^2 * 2^n), which is feasible for n up to about 20.

Smallest Sufficient Team (LC 1125). Find the minimum number of people whose combined skills cover every required skill. Each person's skills are encoded as a bitmask. dp[skillMask] is the minimum people needed to cover the skills in skillMask. Transitions consider adding each person to a smaller state.

Shortest Superstring (LC 943). dp[mask][i] is the shortest string that contains exactly the words in mask and ends with word i. Transitions append a new word with maximum overlap.

When to Use Bitmask DP

Bitmask DP fits when the state has up to roughly 20 boolean dimensions. With n = 20, the mask has 2^20 ≈ 1 million states, which is manageable. Past n = 22 or so, the state space grows too large. Above that, the problem usually requires a different approach (greedy, meet-in-the-middle, or polynomial-time DP on a different parameter).