Back to Study Material Data Structures and Algorithms

Bit Manipulation

Bit manipulation refers to the direct operation on the binary digits (bits) of integers using bitwise operators. Modern CPUs execute bitwise operations in ...

Bit Manipulation

What Is Bit Manipulation and Why Does It Matter

Bit manipulation refers to the direct operation on the binary digits (bits) of integers using bitwise operators. Modern CPUs execute bitwise operations in a single clock cycle, making these techniques significantly faster than equivalent arithmetic or loop-based approaches. In competitive programming and systems programming, the difference between a solution that uses bit tricks and one that does not can be the difference between passing a time limit and receiving a TLE verdict.

The six fundamental bitwise operators are AND (&), OR (|), XOR (^), NOT (~), left shift (<<), and right shift (>>). Each has predictable, consistent behavior across all integer types. For example, x & (x - 1) clears the lowest set bit of x, which allows you to count set bits in O(log n) without a dedicated popcount instruction. Similarly, x & (-x) isolates the lowest set bit, a trick heavily used in Fenwick tree implementations.

Understanding two's complement representation is essential before working with bit manipulation. In two's complement, the most significant bit carries a negative weight, so flipping all bits and adding one negates a number. This means -x equals ~x + 1, which explains why x & (-x) isolates the lowest set bit so elegantly. Knowing the underlying representation prevents subtle bugs when right-shifting signed integers.

Common Bit Manipulation Patterns and Their Applications

Several recurring patterns appear across DSA problems involving bits. Checking whether a number is a power of two is a classic: if n is a power of two, it has exactly one set bit, so n > 0 && (n & (n - 1)) == 0 returns true in O(1). Swapping two integers without a temporary variable uses XOR: a ^= b; b ^= a; a ^= b; — though this trick fails when a and b are the same memory location, so use it carefully.

Bitmask DP is one of the most powerful applications of bit manipulation. When the number of items is small (typically up to 20), you can represent subsets as integers and iterate over all 2^n subsets efficiently. The Travelling Salesman Problem solved with DP has state dp[mask][i] where mask is the bitmask of visited cities and i is the current city, running in O(2^n * n^2) time and O(2^n * n) space.

Extracting and setting individual bits is foundational for these approaches. To read bit k: (x >> k) & 1. To set bit k: x | (1 << k). To clear bit k: x & ~(1 << k). To toggle bit k: x ^ (1 << k). These four operations form the building blocks of virtually every bitmask algorithm. Practicing them until they become instinctive is the single most valuable investment you can make in this topic.

Advanced Tricks: Gray Codes, Subset Enumeration, and Bit Counting

Gray codes are sequences where consecutive values differ by exactly one bit. The n-th Gray code is computed as n ^ (n >> 1). They appear in error correction, combinatorics, and certain DP optimizations where you iterate over subsets and want to minimize the number of operations between consecutive states.

Enumerating all subsets of a given mask m is done with the loop: for (int s = m; s > 0; s = (s - 1) & m). This iterates over every non-empty subset of m in O(3^n) total time across all masks — a key result that makes subset-sum style bitmask DPs feasible. Including the empty subset requires handling s == 0 as a special case after the loop.

Counting the number of set bits (popcount) can be done with Brian Kernighan's algorithm in O(k) where k is the number of set bits: while (x) { count++; x &= x - 1; }. Most modern languages provide a built-in: __builtin_popcount in C++, Integer.bitCount in Java, bin(x).count('1') in Python. Knowing both the manual method and the built-in is important for interviews, where understanding the underlying mechanism matters as much as getting the right answer quickly.