Skip to content
advanced Phase 7 · Advanced Topics

Bit Manipulation

Master bitwise operations for optimization and clever algorithms.

1h 15m
6 problems
Topic Progress 0%

Bit Manipulation Fundamentals

Common Bit Operations

Basic Operations

// Check if bit i is set
boolean isSet(int n, int i) {
    return (n & (1 << i)) != 0;
}

// Set bit i
int setBit(int n, int i) {
    return n | (1 << i);
}

// Clear bit i
int clearBit(int n, int i) {
    return n & ~(1 << i);
}

// Toggle bit i
int toggleBit(int n, int i) {
    return n ^ (1 << i);
}

// Get lowest set bit
int lowestSetBit(int n) {
    return n & (-n);
}

Useful Tricks

// Check if n is power of 2
boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// Count set bits (Brian Kernighan's algorithm)
int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1); // Clear lowest set bit
        count++;
    }
    return count;
}

// Swap without temp variable
void swap(int a, int b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

// Find unique element (all others appear twice)
int findUnique(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

Bitmask Operations

// Generate all subsets of set with n elements
void generateSubsets(int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        // Process subset represented by mask
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                // Element i is in the subset
            }
        }
    }
}

// Check if subset s1 is subset of s2
boolean isSubset(int s1, int s2) {
    return (s1 & s2) == s1;
}

// Union of two sets
int union(int s1, int s2) {
    return s1 | s2;
}

// Intersection of two sets
int intersection(int s1, int s2) {
    return s1 & s2;
}

Time Complexity

  • All basic bit operations: O(1)
  • Iterating over all subsets: O(2^n)
  • Counting bits: O(number of set bits)

Advanced Bit Manipulation

Bit Manipulation DP

Traveling Salesman Problem (TSP)

public int tsp(int[][] dist) {
    int n = dist.length;
    int[][] dp = new int[1 << n][n];
    
    // Initialize with infinity
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
    dp[1][0] = 0; // Start at city 0
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if ((mask & (1 << u)) == 0) continue;
            
            for (int v = 0; v < n; v++) {
                if ((mask & (1 << v)) != 0) continue;
                
                int newMask = mask | (1 << v);
                dp[newMask][v] = Math.min(
                    dp[newMask][v],
                    dp[mask][u] + dist[u][v]
                );
            }
        }
    }
    
    // Find minimum cost to visit all cities and return to 0
    int fullMask = (1 << n) - 1;
    int minCost = Integer.MAX_VALUE;
    for (int u = 1; u < n; u++) {
        minCost = Math.min(minCost, dp[fullMask][u] + dist[u][0]);
    }
    return minCost;
}

Single Number II (Appears Three Times)

public int singleNumber(int[] nums) {
    int ones = 0, twos = 0;
    
    for (int num : nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    
    return ones;
}

Bitwise AND of Numbers Range

public int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    while (left != right) {
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;
}

Reverse Bits

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}

Practice Problems

0 / 1 solved
Single Number
XOR Bit Manipulation

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

Example:

Input: nums = [2,2,1]

Output: 1

1 is the single number.

Solution 
```java
public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}
```

XOR Properties:
- a ^ a = 0 (same numbers cancel)
- a ^ 0 = a (XOR with 0 is identity)
- XOR is commutative and associative

Edge Cases:

  • Single element array
  • Negative numbers
  • Large array with many duplicates

Quiz

1. What is the result of n & (n-1)?

Question 1 options

2. How do you check if a number is a power of 2 using bit manipulation?

Question 2 options

3. What is a common mistake when implementing Bit Manipulation?

Question 3 options

Flashcards

Question

What does XOR (^) do when the same number is applied twice?

Click to reveal answer

Answer

a ^ a = 0. XORing a number with itself gives 0. This property is used to find unique elements in arrays where all others appear twice.

Question

How do you generate all subsets of a set using bitmasks?

Click to reveal answer

Answer

For n elements, iterate mask from 0 to 2^n - 1. If bit i is set in mask, element i is in the subset. This enumerates all 2^n subsets.

Question

Bit Manipulation best practices

Click to reveal answer

Answer

Follow SOLID principles, write clean code, test thoroughly, document decisions, and monitor in production.

Revision Notes

Key Takeaways

  • 1. XOR is powerful for finding unique elements (a ^ a = 0)
  • 2. n & (n-1) clears the lowest set bit - useful for counting bits
  • 3. Bitmasks can represent subsets for combinatorial problems
  • 4. Most bit operations are O(1) constant time
  • 5. Bit manipulation often provides elegant, space-efficient solutions

Interview Tips

  • • XOR problems: look for pairs that cancel out
  • • Use bitmasks when you need to track subset membership
  • • Remember: n & (n-1) clears lowest set bit
  • • For power of 2: check n > 0 && (n & (n-1)) == 0
  • • Practice: Single Number, Number of 1 Bits, Counting Bits, Bitwise AND of Numbers Range

Cheat Sheet

Bit Manipulation Cheat Sheet

Common Operations

n & (1 << i)     // Check if bit i is set
n | (1 << i)     // Set bit i
n & ~(1 << i)    // Clear bit i
n ^ (1 << i)     // Toggle bit i
n & (-n)         // Lowest set bit
n & (n - 1)      // Clear lowest set bit

Useful Properties

  • a ^ a = 0
  • a ^ 0 = a
  • a & a = a
  • a | a = a
  • ~0 = all 1s

Key Tricks

  1. Power of 2: n > 0 && (n & (n-1)) == 0
  2. Count bits: n &= (n-1) in loop
  3. Swap: a ^= b; b ^= a; a ^= b;
  4. Unique element: XOR all elements

Bitmask DP

  • Use bits to represent subsets
  • 1 << n: total subsets
  • mask | (1 << i): add element i
  • mask & (1 << i): check if i in subset

Applications

  1. Find single number (XOR)
  2. Generate all subsets
  3. TSP with bitmask DP
  4. Count set bits
  5. Power of 2 checks