Bit Manipulation from Scratch (2026)
Bit manipulation operates directly on the binary representation of integers using AND (&), OR (|), XOR (^), and shift operators. It provides extremely fast solutions for problems involving subsets, duplicate detection, and parity checks.
Mastering bit tricks—like checking power of two, counting set bits, and bitmasking—is essential for competitive programming and low-level optimization.
Core Bit Operations and Bitmasking
Key bit operations include: get bit (x >> k) & 1, set bit x | (1 << k), clear bit x & ~(1 << k), toggle bit x ^ (1 << k). Bitmasks represent subsets of up to 64 elements using a single integer, enabling efficient DP for traveling salesman and partition problems.
XOR properties are particularly powerful: a ^ a = 0, a ^ 0 = a, making it ideal for finding the unique non-duplicate element and for simple encryption.
const int MAXN = 20;
int dp[1 << MAXN][MAXN];
int tsp(int mask, int pos, vector>& dist) {
if (mask == (1 << MAXN) - 1) return dist[pos][0];
if (dp[mask][pos] != -1) return dp[mask][pos];
int ans = INT_MAX;
for (int city = 0; city < MAXN; city++)
if (!(mask & (1 << city)))
ans = min(ans, dist[pos][city] + tsp(mask | (1 << city), city, dist));
return dp[mask][pos] = ans;
} Power of Two and Bit Tricks
A number is a power of two if (n & (n - 1)) == 0 and n > 0. Counting set bits uses Brian Kernighan's algorithm: iterate n = n & (n - 1) until n becomes 0, counting each iteration. Finding the rightmost set bit uses n & (-n).
These bit tricks solve problems like detecting if a number is a power of two, counting 1 bits (Hamming weight), and finding unique elements in arrays in constant or logarithmic time.
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
int countSetBits(int n) {
int count = 0;
while (n) { n &= (n - 1); count++; }
return count;
}
int rightmostSetBit(int n) { return n & (-n); }Frequently Asked Questions
What is bitmasking used for?
Bitmasking represents subsets as integer bits, enabling O(2^n) DP solutions for combinatorial problems like traveling salesman, subset sum, and graph partitioning with fast bitwise operations.
How does XOR help find unique elements?
XOR of a number with itself gives 0, and XOR with 0 leaves the number unchanged. XORing all elements in an array cancels duplicates, leaving the unique element. This solves 'find the odd occurring number' in O(n) time with O(1) space.
Originally published on Ayodhyyya. Last updated June 1, 2026.