This page collects ready-to-use C++ templates for bit manipulation, fast exponentiation, GCD/LCM, prime sieves, and basic number theory. Each snippet is self-contained — copy it into your solution and adapt as needed. If you’re looking for geometry-related math, see Math & Geometry.

New to Bit Manipulation? Computers store everything in binary. Bit manipulation lets you perform operations on individual bits — it’s incredibly fast and often turns complex problems into elegant one-liners. The most common trick: XOR (a ^ b) cancels matching bits, which is why it solves “single number” problems.

Bit Positions — number 23 = 10111 bit 41 bit 30 bit 21 bit 11 bit 01 16+4+2+1 = 23 XOR Trick — Single Number (all appear twice except one) 4^ 1^ 2^ 1^ 4^ 2 = 4 Pairs cancel (a ^ a = 0), only the unique number survives num & (num-1) clears lowest set bit | num & (-num) gets lowest set bit

Contents

Bit Operations

When to use: You need to inspect, set, clear, or toggle individual bits in a number — common in bitmask DP, permission flags, and encoding state compactly.

Basic Operations

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

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

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

// Check if bit is set
bool isBitSet(int num, int i) {
    return (num >> i) & 1;
}

// Count set bits
int countSetBits(int num) {
    int count = 0;
    while (num) {
        count += num & 1;
        num >>= 1;
    }
    return count;
}

// Count set bits (Brian Kernighan's algorithm)
int countSetBitsFast(int num) {
    int count = 0;
    while (num) {
        num &= (num - 1);
        count++;
    }
    return count;
}

Common Bit Tricks

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

// Clear lowest set bit
int clearLowestSetBit(int num) {
    return num & (num - 1);
}

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

// Get next power of 2
int nextPowerOfTwo(int num) {
    num--;
    num |= num >> 1;
    num |= num >> 2;
    num |= num >> 4;
    num |= num >> 8;
    num |= num >> 16;
    return num + 1;
}

// Swap two numbers
void swap(int& a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}
ID Title Link Solution
29 Divide Two Integers Link Solution
36 Valid Sudoku Link Solution
67 Add Binary Link Solution
191 Number of 1 Bits Link -
231 Power of Two Link -
338 Counting Bits Link -
393 UTF-8 Validation Link Solution
1177 Can Make Palindrome from Substring Link Solution
593 Valid Square Link Solution
2571 Minimum Operations to Reduce an Integer to 0 Link Solution

Common Bit Tricks

When to use: The problem mentions “single number”, “missing number”, “find the duplicate”, or any scenario where XOR’s self-cancelling property (x ^ x = 0) can isolate an answer.

Single Number

// Single Number (all appear twice except one)
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

// Single Number II (all appear three times except one)
int singleNumberII(vector<int>& nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    return ones;
}

Gray Code

vector<int> grayCode(int n) {
    vector<int> result;
    for (int i = 0; i < (1 << n); ++i) {
        result.push_back(i ^ (i >> 1));
    }
    return result;
}
ID Title Link Solution
136 Single Number Link -
137 Single Number II Link -
89 Gray Code Link Solution
389 Find the Difference Link Solution
260 Single Number III Link Solution
2433 Find The Original Array of Prefix Xor Link Solution

Fast Exponentiation

When to use: You need to compute x^n (or modular exponentiation) efficiently — e.g. “pow(x, n)”, matrix exponentiation for DP, or any problem requiring O(log n) power computation.

Power Function

// Fast exponentiation: x^n
double myPow(double x, int n) {
    long long N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    
    double result = 1;
    double current = x;
    
    while (N > 0) {
        if (N % 2 == 1) {
            result *= current;
        }
        current *= current;
        N /= 2;
    }
    
    return result;
}
ID Title Link Solution
50 Pow(x, n) Link Solution

GCD and LCM

When to use: Problems ask for “greatest common divisor”, “least common multiple”, reducing fractions, or checking divisibility relationships between numbers.

// Greatest Common Divisor (Euclidean algorithm)
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Recursive GCD
int gcdRecursive(int a, int b) {
    return b == 0 ? a : gcdRecursive(b, a % b);
}

// Least Common Multiple
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

Prime Numbers

When to use: Problems involve “count primes”, prime factorization, or need to quickly test whether numbers are prime. The sieve is ideal when you need all primes up to N.

Check Prime

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    
    return true;
}

Sieve of Eratosthenes

vector<bool> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    return isPrime;
}

Number Theory

When to use: Problems involve digit manipulation (reverse, palindrome), trailing zeroes in factorials, modular arithmetic, or large number operations.

Factorial Trailing Zeroes

int trailingZeroes(int n) {
    int count = 0;
    while (n > 0) {
        n /= 5;
        count += n;
    }
    return count;
}

Reverse Integer

int reverse(int x) {
    int result = 0;
    while (x != 0) {
        if (result > INT_MAX / 10 || result < INT_MIN / 10) {
            return 0;
        }
        result = result * 10 + x % 10;
        x /= 10;
    }
    return result;
}
ID Title Link Solution
172 Factorial Trailing Zeroes Link -
7 Reverse Integer Link -
9 Palindrome Number Link -
279 Perfect Squares Link Solution
43 Multiply Strings Link Solution
2539 Count the Number of Good Subsequences Link Solution

Quick Reference

Topic Signal Phrases Key Trick
XOR “single number”, “missing number” x ^ x = 0, x ^ 0 = x
Bit counting “number of 1 bits”, “counting bits” n & (n-1) removes lowest set bit
Power of 2 “is power of 2” n & (n-1) == 0
Fast Exponent “pow(x,n)”, “modular exponent” Square-and-multiply
GCD/LCM “greatest common divisor” Euclidean algorithm
Sieve “count primes” Sieve of Eratosthenes

More templates