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
def set_bit(num: int, i: int) -> int:
    return num | (1 << i)


def clear_bit(num: int, i: int) -> int:
    return num & ~(1 << i)


def toggle_bit(num: int, i: int) -> int:
    return num ^ (1 << i)


def is_bit_set(num: int, i: int) -> int:
    return (num >> i) & 1


def count_set_bits(num: int) -> int:
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count


def count_set_bits_kernighan(num: int) -> int:
    count = 0
    while num:
        num &= num - 1
        count += 1
    return count

Common Bit Tricks

def lowest_set_bit(num: int) -> int:
    return num & (-num)


def clear_lowest_set_bit(num: int) -> int:
    return num & (num - 1)


def is_power_of_two(num: int) -> bool:
    return num > 0 and (num & (num - 1)) == 0


def next_power_of_two(num: int) -> int:
    num -= 1
    num |= num >> 1
    num |= num >> 2
    num |= num >> 4
    num |= num >> 8
    num |= num >> 16
    num |= num >> 32
    return num + 1


def xor_swap(a: int, b: int) -> tuple[int, int]:
    a ^= b
    b ^= a
    a ^= b
    return 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)
def single_number(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result


# Single Number II (all appear three times except one)
def single_number_ii(nums: list[int]) -> int:
    ones, twos = 0, 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

Gray Code

def gray_code(n: int) -> list[int]:
    return [i ^ (i >> 1) for i in range(1 << n)]
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
def my_pow(x: float, n: int) -> float:
    N = n
    if N < 0:
        x = 1 / x
        N = -N
    result = 1.0
    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.

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a


def gcd_recursive(a: int, b: int) -> int:
    return a if b == 0 else gcd_recursive(b, a % b)


def lcm(a: int, b: int) -> int:
    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

def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

Sieve of Eratosthenes

def sieve_of_eratosthenes(n: int) -> list[bool]:
    is_p = [True] * (n + 1)
    is_p[0] = is_p[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_p[i]:
            for j in range(i * i, n + 1, i):
                is_p[j] = False
    return is_p

Number Theory

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

Factorial Trailing Zeroes

def trailing_zeroes(n: int) -> int:
    count = 0
    while n > 0:
        n //= 5
        count += n
    return count

Reverse Integer

def reverse_int(x: int) -> int:
    sign = -1 if x < 0 else 1
    x_abs = abs(x)
    r = 0
    while x_abs:
        r = r * 10 + x_abs % 10
        x_abs //= 10
    r *= sign
    if r < -(2**31) or r > 2**31 - 1:
        return 0
    return r
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