Home › Bit Manipulation - DSA Fundamentals

Bit Manipulation

The pattern: Use bitwise operations (AND, OR, XOR, shifts) to solve problems in O(1) space and O(n) time that would otherwise require extra data structures. Bits let you encode states, find unique elements, and perform arithmetic tricks without extra memory.

Why this matters in interviews: Bit manipulation problems look like magic until you know the tricks. They test low-level thinking and mathematical insight. The key operations are few — learn them and you’ll solve any bit problem quickly.

When to Recognize It

How It Works

Think of each number as a row of light switches (bits). Each operation flips, checks, or combines switches:

flowchart LR
    A["AND: both on = on"]:::client
    B["OR: either on = on"]:::service
    C["XOR: different = on"]:::data
    D["NOT: flip all"]:::client

    A --- B
    B --- C
    C --- D

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Essential XOR properties:

Common bit tricks:

Template Code

Code

# Single Number: find the element that appears once (all others twice)
def single_number(nums):
    result = 0
    for num in nums:
        result ^= num  # pairs cancel out
    return result

# Number of 1 bits (Hamming weight)
def hamming_weight(n):
    count = 0
    while n:
        n &= (n - 1)  # clear lowest set bit
        count += 1
    return count

# Missing number: [0..n] with one missing
def missing_number(nums):
    n = len(nums)
    result = n  # start with n (the last index)
    for i in range(n):
        result ^= i ^ nums[i]
    return result

# Counting bits: for each i in [0..n], count set bits
def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp
// Single Number
int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) result ^= num;
    return result;
}

// Number of 1 bits
int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

// Missing number
int missingNumber(int[] nums) {
    int result = nums.length;
    for (int i = 0; i < nums.length; i++) {
        result ^= i ^ nums[i];
    }
    return result;
}

// Counting bits
int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}
// Single Number
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) result ^= num;
    return result;
}

// Number of 1 bits
int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

// Missing number
int missingNumber(vector<int>& nums) {
    int result = nums.size();
    for (int i = 0; i < nums.size(); i++) {
        result ^= i ^ nums[i];
    }
    return result;
}

// Counting bits
vector<int> countBits(int n) {
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}
// Single Number
function singleNumber(nums) {
    let result = 0;
    for (const num of nums) result ^= num;
    return result;
}

// Number of 1 bits
function hammingWeight(n) {
    let count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

// Missing number
function missingNumber(nums) {
    let result = nums.length;
    for (let i = 0; i < nums.length; i++) {
        result ^= i ^ nums[i];
    }
    return result;
}

// Counting bits
function countBits(n) {
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}

Variations

Bitmask DP (Subsets as Integers)

Represent a subset of n elements as an n-bit integer. Bit i is 1 if element i is included. Iterate over all 2^n subsets with a loop from 0 to (1 « n) - 1.

Two Single Numbers

If two numbers appear once (all others twice), XOR all gives a ^ b. Find any set bit in the result (this is where a and b differ). Partition all numbers by that bit — each partition has exactly one unique number.

Reverse Bits

Swap bits from both ends, or build the result bit by bit from LSB to MSB.

Complexity

Operation Time Space
Single Number (XOR) O(n) O(1)
Count 1 bits O(k) where k = set bits O(1)
Missing Number O(n) O(1)
Counting Bits [0..n] O(n) O(n)

Common Mistakes

Practice Problems

Key Takeaways