{"title":"Bit Manipulation","description":null,"content":"Bit manipulation looks intimidating at first. Shifting bits, flipping 1s and 0s, and reading expressions like `n & (n - 1)` takes practice to parse.\n\nBit 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.\n\n> Computers store and process data as bits. Operating on bits directly often leads to shorter, faster solutions than working at the decimal level.\n\nIn this chapter, we will cover:\n\n- What is bit manipulation and why it matters\n- The 6 bitwise operators you need to know\n- Essential bit manipulation techniques\n- Common patterns with sample problems\n- LeetCode problems to practice\n\n---\n\n# What is Bit Manipulation?\n\n**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).\n\nEvery 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.\n\n\n```shell\nDecimal: 5\nBinary: 101\n\nBreakdown:\n 1 × 2² + 0 × 2¹ + 1 × 2⁰\n= 4 + 0 + 1\n= 5\n```\n\n\n### Why Learn Bit Manipulation?\n\n1. **Speed**: Bitwise operations run in a single CPU clock cycle, making them very fast.\n2. **Space Efficiency**: You can store multiple boolean flags in a single integer. Instead of using an array of booleans, one 32-bit integer can hold 32 flags.\n3. **Interview Topic**: Bit manipulation is a common interview topic because it tests fundamental computer science knowledge.\n4. **Compact Solutions**: Some problems that look like they require O(n) space can be solved in O(1) space using bit tricks.\n\n---\n\n# The 6 Bitwise Operators\n\nFirst, here are the six fundamental bitwise operators.\n\n\n\n\n\n### 1. AND (`&`)\n\nReturns `1` only if **both** bits are `1`.\n\n\n```shell\n 5 = 0101\n& 3 = 0011\n-----------\n 1 = 0001\n```\n\n\n**Use case**: Check if a specific bit is set, clear bits, extract bits.\n\n### 2. OR (`|`)\n\nReturns `1` if **at least one** bit is `1`.\n\n\n```shell\n 5 = 0101\n| 3 = 0011\n-----------\n 7 = 0111\n```\n\n\n**Use case**: Set specific bits to 1.\n\n### 3. XOR (`^`)\n\nReturns `1` if the bits are **different**.\n\n\n```shell\n 5 = 0101\n^ 3 = 0011\n-----------\n 6 = 0110\n```\n\n\n**Use case**: Toggle bits, find unique elements, swap values.\n\n**Key property**: `a ^ a = 0` and `a ^ 0 = a`\n\n#### XOR Swap (Without a Temp Variable)\n\nXOR can swap two variables in place:\n\n\n```java\na ^= b;\nb ^= a;\na ^= b;\n// a and b are now swapped without using a temporary variable\n```\n\n\nThis 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.\n\n#### Parity and Single-Number Tricks\n\n`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.\n\nXOR 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.\n\n### 4. NOT (`~`)\n\nFlips all bits (0 becomes 1, 1 becomes 0).\n\n\n```shell\n ~5 = ~0101\n-----------\n = 1010 (in a larger bit representation, this gives -6)\n```\n\n\n**Note**: In most languages, `~n = -(n + 1)` due to two's complement representation.\n\n### 5. Left Shift (`<<`)\n\nShifts bits to the left by specified positions. Each shift **multiplies** by 2.\n\n\n```shell\n5 << 1:\n 0101 << 1\n= 1010\n= 10\n```\n\n\n**Formula**: `n << k = n × 2^k`\n\nThis 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.\n\n### 6. Right Shift (`>>`)\n\nShifts bits to the right by specified positions. Each shift **divides** by 2 (integer division).\n\n\n```shell\n5 >> 1:\n 0101 >> 1\n= 0010\n= 2\n```\n\n\nFor 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`.\n\n### Arithmetic vs Logical Right Shift\n\nJava and JavaScript distinguish two right-shift operators:\n\n- `>>` (arithmetic shift): preserves the sign bit. `-1 >> 1` is still `-1`.\n- `>>>` (logical shift, Java/JS only): fills the leftmost bit with `0`. `-1 >>> 1` becomes `2147483647`.\n\nC++, 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.\n\n---\n\n# Essential Bit Manipulation Techniques\n\nThese techniques appear repeatedly in coding interviews.\n\n### 1. Check if a Bit is Set\n\nTo check if the k-th bit (0-indexed from right) is set to 1:\n\n\n```python\ndef is_bit_set(n, k):\n return (n & (1 << k)) != 0\n```\n\n\n**How it works**:\n\n- `1 << k` creates a number with only the k-th bit set\n- `n & (1 << k)` isolates that bit\n- If the result is non-zero, the bit was set\n\n\n```shell\nExample: Is bit 2 set in 5 (0101)?\n\n1 << 2 = 0100\n5 & 4 = 0101 & 0100 = 0100 (non-zero, so YES)\n```\n\n\n### 2. Set a Bit\n\nTo set the k-th bit to 1:\n\n\n```python\ndef set_bit(n, k):\n return n | (1 << k)\n```\n\n\n**How it works**: OR with a mask that has 1 at position k.\n\n\n```shell\nExample: Set bit 1 in 5 (0101)\n\n1 << 1 = 0010\n5 | 2 = 0101 | 0010 = 0111 = 7\n```\n\n\n### 3. Clear a Bit\n\nTo clear (unset) the k-th bit:\n\n\n```python\ndef clear_bit(n, k):\n return n & ~(1 << k)\n```\n\n\n**How it works**: AND with a mask that has 0 at position k and 1s everywhere else.\n\n\n```shell\nExample: Clear bit 2 in 5 (0101)\n\n1 << 2 = 0100\n~(0100) = 1011\n5 & 11 = 0101 & 1011 = 0001 = 1\n```\n\n\n### 4. Toggle a Bit\n\nTo flip a bit (0 to 1, or 1 to 0):\n\n\n```python\ndef toggle_bit(n, k):\n return n ^ (1 << k)\n```\n\n\n**How it works**: XOR with a mask that has 1 at position k.\n\n### 5. Check if Power of 2\n\nA number is a power of 2 if it has exactly one bit set.\n\n\n```python\ndef is_power_of_two(n):\n return n > 0 and (n & (n - 1)) == 0\n```\n\n\n**How it works**:\n\n- Powers of 2 have only one bit set: 1, 10, 100, 1000...\n- Subtracting 1 flips all bits after (and including) the rightmost set bit\n- AND of these gives 0 only for powers of 2\n\n\n```shell\nn = 8 = 1000\nn - 1 = 0111\nn & n-1 = 0000 (Power of 2!)\n\nn = 6 = 0110\nn - 1 = 0101\nn & n-1 = 0100 (Not power of 2)\n```\n\n\n### 6. Count Set Bits (Brian Kernighan's Algorithm)\n\nCount the number of 1s in the binary representation:\n\n\n```python\ndef count_set_bits(n):\n count = 0\n while n:\n n = n & (n - 1) # Clear the rightmost set bit\n count += 1\n return count\n```\n\n\n**Why it works**: `n & (n - 1)` clears the rightmost set bit. We count how many times we can do this before n becomes 0.\n\n**Time complexity**: O(number of set bits), not O(32)\n\n#### Built-in Bit Counting Primitives\n\nEvery 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.\n\n\n| Language | Function |\n| -------- | -------- |\n| Java | `Integer.bitCount(x)`, `Integer.numberOfTrailingZeros(x)`, `Integer.numberOfLeadingZeros(x)`, `Integer.highestOneBit(x)` |\n| C++ | `__builtin_popcount(x)`, `__builtin_ctz(x)`, `__builtin_clz(x)` (or `std::popcount(x)` in C++20) |\n| Python | `bin(x).count('1')` or `x.bit_count()` (Python 3.10+) |\n| JavaScript | No direct primitive. Use `(x.toString(2).match(/1/g) || []).length` or implement Brian Kernighan |\n| Go | `bits.OnesCount(uint(x))`, `bits.TrailingZeros(uint(x))` in the `math/bits` package |\n| Rust | `x.count_ones()`, `x.trailing_zeros()`, `x.leading_zeros()` |\n| C# | `BitOperations.PopCount(x)` (.NET Core 3.0+) |\n\n\nUse the built-in for production code. The Brian Kernighan trick is still worth knowing for interviews when the question is \"implement popcount from scratch.\"\n\n### 7. Get the Rightmost Set Bit\n\nExtract the rightmost bit that is set to 1:\n\n\n```python\ndef rightmost_set_bit(n):\n return n & (-n)\n```\n\n\n**How it works**: In two's complement, `-n = ~n + 1`. This creates a number where only the rightmost set bit survives the AND.\n\nNote: 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.\n\n\n```shell\nn = 12 = 01100\n-n = -12 = 10100 (two's complement)\nn & -n = 00100 = 4\n```\n\n\n### 8. Turn Off the Rightmost Set Bit\n\n\n```python\ndef clear_rightmost_set_bit(n):\n return n & (n - 1)\n```\n\n\nThis is the same trick used in counting set bits and checking power of 2.\n\n---\n\n# Bitmask as State\n\nA 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` because subset operations become single bitwise instructions.\n\n### Core Operations on a Mask\n\nFor a mask representing a subset:\n\n\n| Operation | Expression |\n| --------- | ---------- |\n| Add element `i` | `mask \\| (1 << i)` |\n| Remove element `i` | `mask & ~(1 << i)` |\n| Check if `i` is set | `(mask & (1 << i)) != 0` |\n| Number of elements | `Integer.bitCount(mask)` |\n| Union of two sets | `mask1 \\| mask2` |\n| Intersection of two sets | `mask1 & mask2` |\n| Set difference (in `mask1`, not `mask2`) | `mask1 & ~mask2` |\n\n\nTo iterate over every element in the mask:\n\n\n```java\nfor (int i = 0; i < n; i++) {\n if (((mask >> i) & 1) == 1) {\n // element i is in the subset\n }\n}\n```\n\n\n### Enumerating Subsets of a Mask\n\nSometimes a problem asks you to enumerate every subset of a given set. The standard trick:\n\n\n```java\n// Enumerate all non-empty subsets of mask, in decreasing order\nfor (int sub = mask; sub > 0; sub = (sub - 1) & mask) {\n process(sub);\n}\n```\n\n\nThis 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.\n\n### Bitmask DP\n\nBitmask DP uses a mask as part of the DP state. Three common examples:\n\n**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.\n\n**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.\n\n**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.\n\n### When to Use Bitmask DP\n\nBitmask 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).\n\n---\n\n# Quiz","pageType":"dsa"}

Bit Manipulation

Get Premium