# Find single number (others appear twice)
result = 0
For num in arr:
    result = result XOR num
Return result


# Prefix XOR (for subarray XOR queries)
prefix[0] = arr[0]
For i in 1 to n-1:
    prefix[i] = prefix[i-1] XOR arr[i]

# XOR of subarray (i..j)
If i == 0:
    return prefix[j]
Else:
    return prefix[j] XOR prefix[i-1]

When to use

• Find unique element
• Subarray XOR
• XOR cancellation problems

Core Principle a XOR a = 0 a XOR 0 = a

Time: O(n)

// Single Number
public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

// Prefix XOR for range queries
public int[] buildPrefixXor(int[] arr) {
    int n = arr.length;
    int[] prefix = new int[n];

    prefix[0] = arr[0];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] ^ arr[i];
    }
    return prefix;
}

public int rangeXor(int[] prefix, int i, int j) {
    if (i == 0) return prefix[j];
    return prefix[j] ^ prefix[i - 1];
}

count = 0
While n > 0:
    n = n & (n - 1)
    count += 1
Return count

When to use

• Count 1s in binary
• Parity check
• Bit complexity problems

Time: O(number of set bits)

public int countSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

If n > 0 AND (n & (n - 1)) == 0:
    return True
Else:
    return False

Why it works Power of 2 has exactly one set bit.

Time: O(1)

public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

# Multiply by 2^k
result = n << k

# Divide by 2^k
result = n >> k

When to use

• Fast multiply/divide by powers of 2
• Bitmask shifting

Right shift differs for signed numbers.

public int multiplyByPowerOfTwo(int n, int k) {
    return n << k;
}

public int divideByPowerOfTwo(int n, int k) {
    return n >> k; // arithmetic shift
}

# Check ith bit
If (n & (1 << i)) != 0:
    bit is set

# Set ith bit
n = n | (1 << i)

# Clear ith bit
n = n & ~(1 << i)

# Toggle ith bit
n = n ^ (1 << i)

When to use

• Bit flags
• State compression
• Bitmask DP

public boolean isBitSet(int n, int i) {
    return (n & (1 << i)) != 0;
}

public int setBit(int n, int i) {
    return n | (1 << i);
}

public int clearBit(int n, int i) {
    return n & ~(1 << i);
}

public int toggleBit(int n, int i) {
    return n ^ (1 << i);
}

For mask in 0 to (1 << n) - 1:
    For i in 0 to n-1:
        If mask & (1 << i):
            include arr[i]

When to use

• Generate all subsets
• TSP / combinatorial DP

Time: O(n × 2ⁿ)

public void generateSubsets(int[] arr) {
    int n = arr.length;

    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}

rightmost = n & (-n)

When to use

• Isolate lowest set bit
• XOR partitioning
• Fenwick Tree logic

Time: O(1)

public int rightmostSetBit(int n) {
    return n & (-n);
}

xor_all = 0
For num in arr:
    xor_all ^= num

set_bit = xor_all & (-xor_all)

num1 = 0
num2 = 0

For num in arr:
    If num & set_bit:
        num1 ^= num
    Else:
        num2 ^= num

Return num1, num2

When to use

• Exactly two unique elements

public int[] twoUniqueNumbers(int[] nums) {
    int xor = 0;
    for (int num : nums) {
        xor ^= num;
    }

    int setBit = xor & (-xor);

    int num1 = 0, num2 = 0;

    for (int num : nums) {
        if ((num & setBit) != 0)
            num1 ^= num;
        else
            num2 ^= num;
    }

    return new int[]{num1, num2};
}

For mask in 0 to (1 << n) - 1:
    If count_set_bits(mask) == k:
        process subset

When to use

• Generate combinations of size k
• Bitmask alternative to backtracking

public void subsetsOfSizeK(int[] arr, int k) {
    int n = arr.length;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (Integer.bitCount(mask) == k) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
        }
    }
}