Minimal, copy-paste Python 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
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

Common Bit Tricks

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

Fast Exponentiation

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

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

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

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

More templates