Bit Manipulation: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Bit Manipulation: Complete Guide with XOR and Bit Tricks

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview. Every template here runs in

O(1)

time for single operations unless otherwise noted.

Main Template: XOR Cancellation

This is the most famous bit manipulation pattern in coding interviews. XOR has two properties that make it invaluable: x ^ x = 0 (a number XORed with itself cancels to zero) and x ^ 0 = x (a number XORed with zero stays unchanged). By XORing every element in an array together, duplicates cancel out and only the unique element remains.

Use this for Single Number .

// XOR every element. Pairs cancel to 0, leaving the
// unique value. Works because XOR is commutative and
// associative so order does not matter.
function singleNumber(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    return result;
}

def single_number(nums: List[int]) -> int:
    result = 0
    for num in nums:
        # XOR accumulates uniquely. Each pair of equal
        # numbers cancels itself out (x ^ x = 0),
        # and the final value is the singleton.
        result ^= num
    return result

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        // Every duplicate pair zeroes itself, leaving
        // only the element that appears once.
        result ^= num;
    }
    return result;
}

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        // XOR is its own inverse. Applying it twice
        // with the same value restores the original,
        // which is exactly why duplicates cancel.
        result ^= num;
    }
    return result;
}

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

result: the accumulator. Starts at 0 because x ^ 0 = x, so the first element seeds the accumulator without special-case logic. After processing every element, result holds the value that appeared an odd number of times.

Visual Mechanism

    stateDiagram-v2
    [*] --> Init: result = 0
    Init --> Process: for each num in nums
    Process --> XOR: result ^= num
    XOR --> Process: next num
    Process --> Done: no more nums
    Done --> [*]: return result

Critical Sections

The XOR accumulator is the entire algorithm. No conditionals, no extra data structures. The key insight is that XOR is commutative and associative, so the order of elements does not matter. Each duplicate pair produces 0 regardless of where it appears in the array, and the unique element survives because it is XORed with 0 at the end.

This pattern extends naturally. Missing Number (problem 3) XORs both indices and values to find the missing element. The same accumulator approach works with a second loop or a different input structure, but the core operation never changes.

Variations

1. Bit Manipulation Utilities

These are the building blocks for any bit-level problem. Each is a one-liner that replaces several lines of conditional logic. Use these when a problem asks you to read, write, or count bits directly.

// Check if bit k is set (1)
function checkBit(n, k) {
    return (n & (1 << k)) !== 0;
}

// Set bit k to 1
function setBit(n, k) {
    return n | (1 << k);
}

// Clear bit k (set to 0)
function clearBit(n, k) {
    return n & ~(1 << k);
}

// Toggle bit k (0 to 1, 1 to 0)
function toggleBit(n, k) {
    return n ^ (1 << k);
}

// Check if n is a power of two
function isPowerOfTwo(n) {
    // Powers of two have exactly one bit set.
    // n-1 flips that bit and clears everything
    // below it, so n & (n-1) is 0.
    return n > 0 && (n & (n - 1)) === 0;
}

// Count set bits (Brian Kernighan's Algorithm)
// Time: O(number of set bits)
function countSetBits(n) {
    let count = 0;
    while (n !== 0) {
        n = n & (n - 1); // clear the lowest set bit
        count++;
    }
    return count;
}

def check_bit(n: int, k: int) -> bool:
    return (n & (1 << k)) != 0

def set_bit(n: int, k: int) -> int:
    return n | (1 << k)

def clear_bit(n: int, k: int) -> int:
    return n & ~(1 << k)

def toggle_bit(n: int, k: int) -> int:
    return n ^ (1 << k)

def is_power_of_two(n: int) -> bool:
    # Powers of two have one bit set.
    # n & (n-1) strips that bit, leaving 0.
    return n > 0 and (n & (n - 1)) == 0

def count_set_bits(n: int) -> int:
    # Kernighan's: each iteration clears one 1-bit,
    # so the loop runs exactly k times for k set bits.
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

boolean checkBit(int n, int k) {
    return (n & (1 << k)) != 0;
}

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

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

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

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

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

bool checkBit(int n, int k) {
    return (n & (1 << k)) != 0;
}

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

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

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

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

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

func checkBit(n, k int) bool {
    return (n & (1 << k)) != 0
}

func setBit(n, k int) int {
    return n | (1 << k)
}

func clearBit(n, k int) int {
    // Go uses &^ for bit clear (AND NOT)
    return n &^ (1 << k)
}

func toggleBit(n, k int) int {
    return n ^ (1 << k)
}

func isPowerOfTwo(n int) bool {
    return n > 0 && (n & (n - 1)) == 0
}

func countSetBits(n int) int {
    count := 0
    for n != 0 {
        n &= (n - 1)
        count++
    }
    return count
}

Visual: How `n & (n - 1)` Works

    graph LR
    I["n = 12 (1100)"] --> S["n - 1 = 11 (1011)"]
    I --> A["n & (n - 1)"]
    S --> A
    A --> R["Result = 8 (1000)"]

Subtracting 1 flips the lowest set bit to 0 and all lower bits to 1. ANDing with the original clears that bit while leaving higher bits unchanged. Repeating this counts each set bit exactly once.

Visual: Bit Operations on a 4-bit Integer

    graph TD
    subgraph Original
        O["n = 5 (0101)"]
    end
    subgraph Check
        C["Bit 2? (0101) & (0100) = 0100 != 0 => true"]
    end
    subgraph Set
        S["Set bit 1: 0101 | 0010 = 0111 (7)"]
    end
    subgraph Clear
        CL["Clear bit 2: 0101 & 1011 = 0001 (1)"]
    end
    subgraph Toggle
        T["Toggle bit 0: 0101 ^ 0001 = 0100 (4)"]
    end

    O --> C
    O --> S
    O --> CL
    O --> T

2. Subset Generation

A bitmask represents each subset as a binary number. For an array of n elements, there are 2^n subsets. Mask i has its j-th bit set when element j belongs to the subset. This is how DP over subsets internalizes state.

Use this for Subsets .

// Time: O(N * 2^N)  Space: O(1) excluding output
function subsets(nums) {
    const output = [];
    const n = nums.length;
    // Each mask from 0 to 2^n - 1 represents one subset.
    // Bit j being set means nums[j] is included.
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset = [];
        for (let j = 0; j < n; j++) {
            if ((mask & (1 << j)) !== 0) {
                subset.push(nums[j]);
            }
        }
        output.push(subset);
    }
    return output;
}

def subsets(nums: List[int]) -> List[List[int]]:
    output = []
    n = len(nums)
    for mask in range(1 << n):
        subset = []
        for j in range(n):
            # Check if the j-th element is included
            # by testing the j-th bit of the mask.
            if (mask & (1 << j)):
                subset.append(nums[j])
        output.append(subset)
    return output

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> output = new ArrayList<>();
    int n = nums.length;

    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if ((mask & (1 << j)) != 0) {
                subset.add(nums[j]);
            }
        }
        output.add(subset);
    }
    return output;
}

Visual

    graph LR
    M0["Mask 0 (000): []"] --> M1["Mask 1 (001): [a]"]
    M1 --> M2["Mask 2 (010): [b]"]
    M2 --> M3["Mask 3 (011): [a, b]"]
    M3 --> M4["Mask 4 (100): [c]"]
    M4 --> M5["..."]

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .

Bit Manipulation: Code Templates in 6 Languages

Main Template: XOR Cancellation

Code Breakdown

Key Variables

Visual Mechanism

Critical Sections

Variations

1. Bit Manipulation Utilities

Visual: How n & (n - 1) Works

Visual: Bit Operations on a 4-bit Integer

2. Subset Generation

Visual

Visual: How `n & (n - 1)` Works