Minimal, copy-paste Java for bit operations, fast exponentiation, GCD/LCM, primes, and number theory. See also Math & Geometry.

Contents

Bit Operations

Basic Operations

// 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) {
        count += num 1;
        num >>= 1;
    }
    return count;
}

// Count set bits (Brian Kernighan's algorithm)
static int countSetBitsFast(int num) {
    int count = 0;
    while (num) {
        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

Single Number

// 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) {
    int[]result;
    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

Power Function

// 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

// 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

Check Prime

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

Factorial Trailing Zeroes

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