This page collects ready-to-use Java 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

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 |

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

Common Bit Tricks

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 
// Set bit at position i
static int setBit(int num, int i) {
    return num | (1 << i);
}

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

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

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

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

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

Common Bit Tricks

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

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

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

// Get next power of 2
static 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
static 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

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

Gray Code

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 
// Single Number (all appear twice except one)
static int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

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

Gray Code

int[]grayCode(int n) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < (1 << n); ++i) {
        result.add(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

ID Title Link Solution
50 Pow(x, n) Link Solution 
// Fast exponentiation: x^n
static double myPow(double x, int n) {
    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)
static int gcd(int a, int b) {
    while (b !) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

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

// Least Common Multiple
static 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

Sieve of Eratosthenes

static boolean 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

boolean[]sieveOfEratosthenes(int n) {
    boolean[]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

Reverse Integer

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 
static int trailingZeroes(int n) {
    int count = 0;
    while (n > 0) {
        n /= 5;
        count += n;
    }
    return count;
}

Reverse Integer

static int reverse(int x) {
    int result = 0;
    while (x !) {
        if (result > Integer.MAX_VALUE / 10 || result < Integer.MIN_VALUE / 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

More templates