Master low-level bit operations to solve complex problems with elegant efficiency. Learn binary arithmetic, bitwise operators, bit tricks, and leverage bitmasks for dynamic programming. Essential for optimizing algorithms and acing technical interviews.
Numbers in computers are sequences of bits (0s and 1s). Each position represents a power of 2.
Divide repeatedly by 2 and collect remainders.
// 13 decimal = 1101 binary (8 + 4 + 1) public static string DecimalToBinary(int n) { if (n == 0) return "0"; string result = ""; while (n > 0) { result = (n % 2) + result; n /= 2; } return result; } // Or: Convert.ToString(13, 2) → "1101"
| Type | Bits | Range |
|---|---|---|
| byte | 8 | 0 to 255 |
| sbyte | 8 | -128 to 127 |
| short | 16 | -32k to 32k |
| int | 32 | ±2.1B |
| long | 64 | ±9.2Q |
Negative numbers use two's complement: flip all bits, then add 1.
// 5 in 8-bit: 0000 0101 → Flip: 1111 1010 → Add 1: 1111 1011 = -5 public static int GetNegation(int n) { return (~n) + 1; } // Right shift difference: signed vs unsigned int x = -8; // Arithmetic shift: fills with sign bit x >> 1; // -4 uint y = 4294967288; // Same bits as -8 (unsigned) y >> 1; // 2147483644 (fills with 0)
Six core operators: AND (&), OR (|), XOR (^), NOT (~), Left Shift (<<), Right Shift (>>).
int a = 5; // 0101 int b = 3; // 0011 int c = a & b; // 0001 = 1 // Check if i-th bit is set bool isBitSet = (n & (1 << i)) != 0;
int a = 5; // 0101 int b = 3; // 0011 int c = a | b; // 0111 = 7 // Set i-th bit to 1 int result = n | (1 << i);
int a = 5; // 0101 int b = 3; // 0011 int c = a ^ b; // 0110 = 6 // Toggle (flip) i-th bit int result = n ^ (1 << i);
int a = 5; // 0000...0101 int b = ~a; // 1111...1010 = -6 (two's complement)
int a = 5; // 0101 int b = a << 1; // 1010 = 10 int c = a << 2; // 10100 = 20
int a = 16; // 10000 int b = a >> 1; // 01000 = 8 // For signed: fills with sign bit (arithmetic) int neg = -8 >> 1; // -4
Essential bit manipulation patterns for interviews.
// Least significant bit (LSB) tells us: 0 = even, 1 = odd public static bool IsOdd(int n) => (n & 1) == 1; public static bool IsEven(int n) => (n & 1) == 0;
// Powers of 2: 1 (0001), 2 (0010), 4 (0100), 8 (1000)... // All have exactly one bit set. Key insight: n & (n-1) removes the rightmost bit. // If n is power of 2, n & (n-1) == 0 public static bool IsPowerOfTwo(int n) => n > 0 && (n & (n - 1)) == 0; // Example: 8 (1000) & 7 (0111) = 0000 ✓
public static bool GetBit(int n, int i) => (n & (1 << i)) != 0; // Example: GetBit(13, 0) = 1 (13 = 1101, rightmost = 1)
public static int SetBit(int n, int i) => n | (1 << i); // Example: SetBit(8, 0) = 9 (1000 | 0001 = 1001)
public static int ClearBit(int n, int i) => n & ~(1 << i); // Example: ClearBit(13, 0) = 12 (1101 & 1110 = 1100)
public static int ToggleBit(int n, int i) => n ^ (1 << i); // Example: ToggleBit(13, 1) = 15 (1101 ^ 0010 = 1111)
// n & (n-1) removes the rightmost set bit each iteration public static int CountSetBits(int n) { int count = 0; while (n > 0) { n &= n - 1; // Remove rightmost set bit count++; } return count; } // Time: O(number of set bits), not O(32) // Example: CountSetBits(13) → 3 (1101 has three 1s)
// n & (-n) isolates the rightmost set bit // Why? -n is two's complement of n public static int RightmostSetBit(int n) => n & -n; // Example: RightmostSetBit(13) = 1 (13 = 1101, rightmost bit = 1) // Example: RightmostSetBit(12) = 4 (12 = 1100, rightmost bit = 0100)
XOR has special properties that make it ideal for many interview problems.
int a = 5, b = 3; a = a ^ b; b = a ^ b; // b now = original a a = a ^ b; // a now = original b // But: Modern compilers optimize this; temp swap is clearer
// XOR all numbers. Pairs cancel (a^a=0), leaving the single. public static int FindSingle(int[] nums) { int result = 0; foreach (int num in nums) result ^= num; return result; } // Example: [2, 2, 1, 3, 3] → 1 (2^2 cancels, 3^3 cancels)
Use bitmasks to represent sets, track state, or enumerate subsets efficiently.
// Mask with i-th bit set: (1 << i) int mask1 = 1 << 3; // 1000 = bit 3 // Mask with bits [0..i] set: (1 << (i+1)) - 1 int mask2 = (1 << 4) - 1; // 1111 = bits 0-3 // Mask to isolate rightmost i bits: n & ((1 << i) - 1) int n = 13; // 1101 int lower2 = n & 3; // 01 = 1 (rightmost 2 bits)
// Represent each subset as a bitmask (0 to 2^n - 1) public static void EnumerateSubsets(int[] arr) { int n = arr.Length; for (int mask = 0; mask < (1 << n); mask++) { // Process subset represented by mask List<int> subset = new(); for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0) subset.Add(arr[i]); // Use subset... } } // Time: O(n * 2^n) - explores 2^n subsets
// Example: Count subsets with even sum public static int CountEvenSubsets(int[] arr) { int n = arr.Length; int count = 0; for (int mask = 0; mask < (1 << n); mask++) { int sum = 0; for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0) sum += arr[i]; if (sum % 2 == 0) count++; } return count; } // Time: O(n^2 * 2^n) - can optimize with DP
Combine bit masks with dynamic programming for subset and state-based problems.
// dp[mask] = some result for subset represented by mask public static int SubsetDP(int[] arr) { int n = arr.Length; int[] dp = new int[1 << n]; dp[0] = 0; // Base case: empty set // Process each subset for (int mask = 1; mask < (1 << n); mask++) { // Try removing each element to get previous state for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) { int prevMask = mask ^ (1 << i); // dp[mask] = f(dp[prevMask], arr[i]) } } } return dp[(1 << n) - 1]; // All elements } // Space: O(2^n), Time: O(n * 2^n)
// dp[mask][i] = min cost to visit cities in mask, ending at city i public static int TSP(int[][] dist) { int n = dist.Length; int[][] dp = new int[1 << n][]; for (int i = 0; i < (1 << n); i++) dp[i] = new int[n]; // Base: start at city 0 for (int i = 0; i < n; i++) dp[1][i] = int.MaxValue; dp[1][0] = 0; // Fill DP table for (int mask = 1; mask < (1 << n); mask++) { for (int u = 0; u < n; u++) { if ((mask & (1 << u)) == 0) continue; if (dp[mask][u] == int.MaxValue) continue; for (int v = 0; v < n; v++) { if ((mask & (1 << v)) == 0) { int newMask = mask | (1 << v); dp[newMask][v] = Math.Min(dp[newMask][v], dp[mask][u] + dist[u][v]); } } } } // Return cost to visit all cities, ending at city 0 int ans = int.MaxValue; for (int i = 0; i < n; i++) ans = Math.Min(ans, dp[(1 << n) - 1][i]); return ans; } // Time: O(n^2 * 2^n), Space: O(n * 2^n)
Bit-Level Explanation: XOR cancels pairs (a^a=0), leaving the single element.
public class Solution { public int SingleNumber(int[] nums) { int result = 0; foreach (int num in nums) result ^= num; return result; } } // Example: [2, 2, 1] → 1 (2^2=0, 0^1=1) // Time: O(n), Space: O(1)
Bit-Level Explanation: Count each bit position across all numbers. Modulo 3 gives the single number's bits.
public int SingleNumberII(int[] nums) { int[] bits = new int[32]; foreach (int num in nums) { for (int i = 0; i < 32; i++) { if ((num & (1 << i)) != 0) bits[i]++; } } int result = 0; for (int i = 0; i < 32; i++) { if (bits[i] % 3 != 0) result |= (1 << i); } return result; } // Time: O(32n), Space: O(32)
Bit-Level Explanation: XOR all elements to get a^b. Find a differing bit. Partition by that bit, XOR each group.
public int[] SingleNumberIII(int[] nums) { int xorAll = 0; foreach (int num in nums) xorAll ^= num; // xorAll = a ^ b // Find rightmost differing bit int diffBit = xorAll & -xorAll; int a = 0, b = 0; foreach (int num in nums) { if ((num & diffBit) != 0) a ^= num; else b ^= num; } return new int[] { a, b }; } // Time: O(n), Space: O(1)
// Method 1: Brian Kernighan (optimal for sparse bits) public int HammingWeight(uint n) { int count = 0; while (n > 0) { n &= n - 1; count++; } return count; } // Method 2: Built-in (C# 5.0+) return System.Numerics.BitOperations.PopCount(n);
Bit-Level Explanation: i & (i-1) removes rightmost bit. dp[i] = dp[i & (i-1)] + 1.
public int[] CountBits(int n) { int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) dp[i] = dp[i & (i - 1)] + 1; return dp; } // Example: n=2 → [0, 1, 1] // Time: O(n), Space: O(n)
public uint ReverseBits(uint n) { uint result = 0; for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) result |= (1u << (31 - i)); } return result; } // Example: 43261596 (00000010100101000001111010011100) // → 964176192 (00111001011110000010100101000000) // Time: O(32), Space: O(1)
Bit-Level Explanation: Powers of 2 have exactly one bit set. n & (n-1) == 0 identifies them.
public bool IsPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } // Example: IsPowerOfTwo(16) = true (10000 & 01111 = 0) // Time: O(1), Space: O(1)
Bit-Level Explanation: XOR array with 0..n. Pairs cancel, leaving missing.
public int MissingNumber(int[] nums) { int result = 0; for (int i = 0; i < nums.Length; i++) result ^= i ^ nums[i]; result ^= nums.Length; return result; } // Example: [3, 0, 1] → 2 // 0^3 ^ 1^0 ^ 2^1 ^ 3 = 2 // Time: O(n), Space: O(1)
Bit-Level Explanation: XOR gives sum without carry. AND << 1 gives carry. Repeat until no carry.
public int GetSum(int a, int b) { while (b != 0) { int carry = (a & b) << 1; // Carry bits a = a ^ b; // Sum without carry b = carry; // Process carry } return a; } // Example: GetSum(1, 2) // a=1 (01), b=2 (10) // Iteration 1: carry=0, a=3, b=0 → return 3 // Note: Works for positive; needs unchecked for negative
Bit-Level Explanation: Common prefix of m and n remains; all other bits become 0.
public int RangeBitwiseAnd(int m, int n) { int shift = 0; // Find common prefix by right-shifting both m and n while (m != n) { m >>= 1; n >>= 1; shift++; } // Restore the common prefix return m << shift; } // Example: RangeBitwiseAnd(5, 7) // 5=101, 6=110, 7=111 → AND=100=4 // Common prefix after shifting: 1 → shift left by 2 → 100 // Time: O(log(min(m,n))), Space: O(1)
public IList<IList<int>> Subsets(int[] nums) { var result = new List<IList<int>>(); int n = nums.Length; for (int mask = 0; mask < (1 << n); mask++) { var subset = new List<int>(); for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) subset.Add(nums[i]); } result.Add(subset); } return result; } // Example: nums=[1,2,3] // mask=000 → [], 001 → [1], 010 → [2], 011 → [1,2], // 100 → [3], 101 → [1,3], 110 → [2,3], 111 → [1,2,3] // Time: O(n * 2^n), Space: O(n * 2^n)
Bit-Level Explanation: Build trie of bit patterns. For each number, greedily pick opposite bit at each level.
public int FindMaximumXOR(int[] nums) { // Build trie of 32-bit numbers TrieNode root = new TrieNode(); foreach (int num in nums) { TrieNode node = root; for (int i = 31; i >= 0; i--) { int bit = (num >> i) & 1; if (node.children[bit] == null) node.children[bit] = new TrieNode(); node = node.children[bit]; } } int maxXor = 0; foreach (int num in nums) { TrieNode node = root; int currentXor = 0; for (int i = 31; i >= 0; i--) { int bit = (num >> i) & 1; int oppBit = 1 - bit; // Prefer opposite if (node.children[oppBit] != null) { currentXor |= (1 << i); node = node.children[oppBit]; } else { node = node.children[bit]; } } maxXor = Math.Max(maxXor, currentXor); } return maxXor; } private class TrieNode { public TrieNode[] children = new TrieNode[2]; } // Time: O(32n), Space: O(32n)
Bit-Level Explanation: UTF-8: single byte 0xxxxxxx; multi-byte 1xxxxxxx followed by 10xxxxxx bytes.
public bool ValidUtf8(int[] data) { int bytesRemaining = 0; foreach (int d in data) { int byte_ = d & 0xFF; // Keep only last 8 bits if (bytesRemaining == 0) { if ((byte_ >> 7) == 0) bytesRemaining = 0; // 0xxxxxxx else if ((byte_ >> 5) == 6) bytesRemaining = 1; // 110xxxxx else if ((byte_ >> 4) == 14) bytesRemaining = 2; // 1110xxxx else if ((byte_ >> 3) == 30) bytesRemaining = 3; // 11110xxx else return false; } else { if ((byte_ >> 6) != 2) return false; // Must be 10xxxxxx bytesRemaining--; } } return bytesRemaining == 0; } // Time: O(n), Space: O(1)
public int HammingDistance(int x, int y) { int xor = x ^ y; int count = 0; while (xor > 0) { xor &= xor - 1; // Remove rightmost set bit count++; } return count; } // Example: x=1 (01), y=4 (100) // XOR = 101 → two 1 bits → Hamming distance = 2 // Time: O(# set bits), Space: O(1)
Bit-Level Explanation: For each bit position, count 0s and 1s. Contribution = (count0 * count1).
public int TotalHammingDistance(int[] nums) { int n = nums.Length; int total = 0; for (int i = 0; i < 32; i++) { int ones = 0; foreach (int num in nums) { if ((num & (1 << i)) != 0) ones++; } int zeros = n - ones; total += ones * zeros; // Pairs with differing bit } return total; } // Example: [1, 3, 5] // Bit 0: 3 ones, 0 zeros → 0 // Bit 1: 1 one, 2 zeros → 2 // Bit 2: 2 ones, 1 zero → 2 // Total = 4 // Time: O(32n), Space: O(1)
| Precedence | Operator | Note |
|---|---|---|
| 1 (Highest) | ~ (NOT) | Unary, evaluated right-to-left |
| 2 | << and >> | Shifts bind tighter than comparisons |
| 3 | & (AND) | Tighter than ^ and | |
| 4 | ^ (XOR) | |
| 5 | | (OR) | Loosest of bitwise ops |
| 6 | ==, != | Comparison operators |
n & 1 << 2 = n & (1 << 2), not (n & 1) << 2// WRONG: Check if bit 2 is set if (n & 1 << 2) { } // Evaluated as n & (1 << 2) ✓ but accidentally correct // WRONG: Comparison with bitwise if (n & 1 == 1) { } // = n & (1 == 1) = n & 1 (wrong semantics) // RIGHT if ((n & 1) == 1) { }
// Right shift behavior differs for signed vs unsigned int x = -8; // Arithmetic shift (fills with sign bit) x >> 1; // -4 uint y = (uint)-8; // Cast to unsigned y >> 1; // Large positive (logical shift) // For absolute right shift (logical): use unsigned or cast uint logical = ((uint)x) >> 1;
(n & (1 << i)) is clearer than n & 1 << i.unchecked in C# if intentional, or use long.using System.Numerics; // Count set bits (population count) int setBits = BitOperations.PopCount(13); // 3 // Leading zero count int leadingZeros = BitOperations.LeadingZeroCount(8); // 28 (in 32-bit) // Trailing zero count int trailingZeros = BitOperations.TrailingZeroCount(8); // 3 // Rotate bits int rotated = BitOperations.RotateLeft(5, 2); // Left rotate
Rare but powerful techniques for highly optimized bit manipulation.
Binary encoding where successive values differ by one bit. Useful in error detection and digital electronics.
// Convert binary to Gray code public static int BinaryToGray(int n) => n ^ (n >> 1); // Convert Gray code back to binary public static int GrayToBinary(int gray) { int binary = gray; while (gray > 0) { gray >>= 1; binary ^= gray; } return binary; } // Example: 5 (binary 0101) → 0111 (Gray) // Gray 0111 → 0101 (back to 5)
// Parity: is popcount odd or even? public static bool HasOddParity(int n) { n ^= n >> 16; n ^= n >> 8; n ^= n >> 4; n ^= n >> 2; n ^= n >> 1; return (n & 1) == 1; } // Nearest power of 2 greater than n public static int NextPowerOfTwo(int n) { n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; return n + 1; } // Example: NextPowerOfTwo(5) = 8, NextPowerOfTwo(8) = 16
Interleave bits of two numbers for spatial indexing.
// Interleave bits of x and y public static ulong Interleave(uint x, uint y) { ulong result = 0; for (int i = 0; i < 32; i++) { result |= (((ulong)x & (1u << i)) << i) | (((ulong)y & (1u << i)) << (i + 1)); } return result; } // Example: x=3 (11), y=2 (10) → 1101 (interleaved) // Bit positions: y[1] x[1] y[0] x[0] = 1 1 1 1
// Find rightmost bit position where two numbers differ public static int RightmostDifferenceBit(int a, int b) { int xor = a ^ b; return xor & -xor; // Isolate rightmost set bit } // Example: a=5 (0101), b=3 (0011) → XOR=0110 → rightmost=0010
// Check if all set bits of 'a' are also set in 'b' public static bool IsBitSubset(int a, int b) { return (a & b) == a; } // Example: a=5 (0101), b=7 (0111) → (0101 & 0111) = 0101 = 5 ✓ // Example: a=6 (0110), b=5 (0101) → (0110 & 0101) = 0100 ≠ 6 ✗
Where bit manipulation actually matters in production code:
| Pattern | Code | Use Case |
|---|---|---|
| Check bit i | (n >> i) & 1 | Test single bit |
| Set bit i | n | (1 << i) | Enable flag |
| Clear bit i | n & ~(1 << i) | Disable flag |
| Toggle bit i | n ^ (1 << i) | Switch state |
| Check if power of 2 | (n & (n-1)) == 0 | Validate magnitude |
| Rightmost set bit | n & -n | Isolate LSB |
| Remove rightmost set | n & (n-1) | Decrement bits |
| Count set bits | while(n) n&=n-1; count++ | Population count |
| Isolate difference | a ^ b | Find changes |
| Merge options | a | b | Combine flags |
Understanding the computational cost of bitwise operations:
Convert.ToString(n, 2) shows you exactly what's happening at each step.// Debug helper: visualize bit operations public static void DebugBits(int n, string label = "") { string binary = Convert.ToString(n, 2).PadLeft(32, '0'); Console.WriteLine($"{label,-20} {n,12} {binary}"); } // Usage: int x = 5; DebugBits(x, "Original"); DebugBits(x << 1, "After << 1"); DebugBits(x & 3, "After & 3"); // Output shows binary clearly for verification
Fast algorithms for subset enumeration and sum over subsets.
Iterate all submasks of a bitmask in O(3^n) total time across all masks.
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) { // Each submask is processed exactly once } // Key: (submask - 1) & mask gives next smaller submask // Example mask = 1101 (13): submasks are 1101, 1100, 1001, 1000, 0101, 0100, 0001
Compute sum of values for all submasks of each mask in O(n * 2^n) time.
public static int[] SumOverSubsets(int[] arr, int maxBits) { int n = 1 << maxBits; int[] dp = new int[n]; Array.Copy(arr, dp, Math.Min(arr.Length, n)); for (int i = 0; i < maxBits; i++) { for (int mask = 0; mask < n; mask++) { if ((mask & (1 << i)) != 0) dp[mask] += dp[mask ^ (1 << i)]; } } return dp; } // Time: O(maxBits * 2^maxBits), Space: O(2^maxBits)
Micro-optimizations using bit manipulation in critical code paths.
// Modulo by power of 2 is much faster as AND operation int slow = n % 16; // Division: 5-20 cycles int fast = n & 15; // AND: 1 cycle (15 = 16 - 1 = 0xF) // General rule: n % 2^k = n & (2^k - 1) // The low k bits of n equal n mod 2^k
// Returns 1 if x > 0, -1 if x < 0, 0 if x == 0 public static int Sign(int x) { return (x >> 31) | (-x >> 31); } // Why? If x > 0: first shift = 0, second shift = 0, OR = 0 // If x < 0: first shift = -1, second shift = 0, OR = -1 // Hmm, this returns -1 not 1. Better version: public static int SignCorrect(int x) { return ((x >> 31) & -2) + (x > 0 ? 1 : 0); }
public static int AbsBranchless(int x) { int signMask = x >> 31; // -1 if negative, 0 if positive return (x + signMask) ^ signMask; } // Logic: if negative, add -1 then XOR with -1 (flip all bits) // This applies two's complement: -x = ~x + 1
Mistakes that catch experienced programmers when working with bits.
1 << 31 overflows in signed 32-bit. Use long or limit shifts to 30.// WRONG int mask = (1 << 31) - 1; // Overflow before subtraction // CORRECT long mask = (1L << 31) - 1; // 0x7FFFFFFF int mask2 = -1; // All bits set (0xFFFFFFFF)
// Signed: arithmetic shift (extends sign bit) int x = -8; x >> 2; // -2 (fills with 1s) // Unsigned: logical shift (fills with 0s) uint y = 4294967288; // Same bits as -8 y >> 2; // 1073741822 (fills with 0s)
// CONFUSING: Check if bit i is set if (n & 1 << i) { } // Works but misleading // CLEAR: Explicitly show what you mean if ((n & (1 << i)) != 0) { } // WRONG: Comparison operator has lower precedence than AND if (n & 1 == 1) { } // Evaluates as n & (1 == 1) = n & 1 // RIGHT if ((n & 1) == 1) { }
// XOR SWAP with same variable: BROKEN int a = 5; a ^= a; // a becomes 0 a ^= a; // a remains 0 a ^= a; // a remains 0 -- NOT 5! // Use temp swap: clearer and faster on modern CPUs int temp = a; a = b;Quick Reference & Cheat Sheet
A compact summary of all bit manipulation techniques for quick lookup during interviews.
One-Line Bit Operations
Operation Code Returns Get bit i (n >> i) & 1 0 or 1 Set bit i n | (1 << i) n with bit i=1 Clear bit i n & ~(1 << i) n with bit i=0 Toggle bit i n ^ (1 << i) n with bit i flipped Check if even (n & 1) == 0 true/false Check if power of 2 (n & (n-1)) == 0 && n > 0 true/false Rightmost set bit n & -n isolates LSB Remove rightmost set n & (n-1) clears LSB Count set bits System.Numerics.BitOperations.PopCount(n) count of 1s Isolate lower k bits n & ((1 << k) - 1) bottom k bits Bitmask DP Template
// Enumerate all subsets: O(2^n) for (int mask = 0; mask < (1 << n); mask++) { // Process subset represented by mask } // Enumerate all submasks: O(3^n total) for (int submask = mask; submask > 0; submask = (submask - 1) & mask) { // Process submask } // DP over subsets: O(n * 2^n) or O(n^2 * 2^n) int[] dp = new int[1 << n]; dp[0] = 0; // Base case: empty set for (int mask = 1; mask < (1 << n); mask++) { // Try removing each element for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) { int prev = mask ^ (1 << i); // dp[mask] = f(dp[prev], element[i]) } } }XOR Properties Quick Lookup
a ^ a = 0Any value XORed with itself is 0.a ^ 0 = aXORing with 0 is identity operation.a ^ b = b ^ aXOR is commutative.(a ^ b) ^ c = a ^ (b ^ c)XOR is associative.a ^ a ^ b = bPairs cancel; use for finding unpaired elements.a ^ (~a) = all 1sXORing a value with its inverse gives full mask.Interview Question Classification
By XOR: Single Number (136), Single Number II (137), Single Number III (260), Missing Number (268)
By Counting Bits: Number of 1 Bits (191), Counting Bits (338), Hamming Distance (461), Total Hamming Distance (477)
By Bit Tricks: Power of Two (231), Reverse Bits (190), Sum of Two Integers (371)
By Bitmask: Subsets (78), Maximum XOR (421), UTF-8 Validation (393), Bitwise AND of Range (201)
By DP: Travelling Salesman, Maximum Weight Independent Set, Assign Cookies to Groups
Complexity Reference
Approach Time Space When to Use Single Pass (XOR) O(n) O(1) Unpaired elements, simple XOR tricks Bit Counting Loop O(k * n) where k=popcount O(32) or O(64) Counting bits in array Subset Enumeration O(n * 2^n) O(1) Small n ≤ 20, checking all subsets Submask DP O(3^n) O(2^n) Dependency between subsets, n ≤ 20 Bitmask DP O(n^2 * 2^n) O(n * 2^n) TSP, Hamiltonian paths, n ≤ 16 Last-Minute Tips for Interviews
1Draw Binary RepresentationsWrite out bit patterns for small examples. Patterns become obvious visually.2Test Edge Cases FirstTest with 0, -1, 1, powers of 2, max/min values. Bit ops surprise often.3Use Parentheses AlwaysEven if operator precedence seems clear, add parentheses. Clarity > cleverness.4Know Your PrimitivesUnderstand bit widths (int=32, long=64) and signed vs unsigned behavior in your language.5Recognize XOR Patterns InstantlyProblems with unpaired elements, swapping, or toggling often scream for XOR.6n & (n-1) is Your Best FriendRemoves rightmost set bit. Essential for counting, powers of 2, and many tricks.b = temp; ConclusionMastering Bit Manipulation
Bit manipulation bridges the gap between high-level algorithms and low-level hardware efficiency. It's a skillset that compounds: early mastery pays dividends across interviews, competitive programming, and optimization-critical code.
Your Learning Path Forward
1Memorize Basics: Operator truth tables, two's complement, bit widths in your language. Spend one day here.2Learn Tricks: Power of 2 check, count bits, set/clear/toggle bits. Practice on LeetCode Easy tier (191, 231, 461).3Master XOR: Work through all XOR-based problems (136, 137, 260, 268). XOR is the gateway to intermediate problems.4Solve Medium Problems: Tackle mask-based problems and DP (78, 421, 338, 477). Understand bitmask DP template thoroughly.5Challenge Yourself: Solve hard problems and competitive programming problems. Implement TSP, SOS DP, and advanced techniques.6Optimize & Teach: Optimize your solutions for speed/space. Explain bit tricks to others to deepen understanding.Resources for Continued Learning
Practice Platforms: LeetCode (sorted by topic), Codeforces (bit manipulation tag), AtCoder, HackerRank. Do 30-50 problems across difficulties.Advanced Topics: After mastering this chapter, explore Gray code, Hamming codes, cryptography basics, and GPU/SIMD bit-level parallelism.Final Checklist Before an Interview
Can you answer "yes" to all?
Know Your FoundationsExplain two's complement from scratchDraw why n & (n-1) removes the rightmost bitList all 6 bitwise operators and their usesExplain signed vs unsigned right shiftSolve Common ProblemsSingle Number variants (15 min each)Bit counting and XOR swaps (10 min each)Power of 2 and bit tricks (5 min each)Bitmask subset enumeration (20 min)Now go solve bit problems and ace that interview.