Bit Manipulation

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)

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;
}