Minimal, copy-paste C++ 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 setBit(self, num, i):
    return num | (1 << i)
# Clear bit at position i
def clearBit(self, num, i):
    return num  ~(1 << i)
# Toggle bit at position i
def toggleBit(self, num, i):
    return num ^ (1 << i)
# Check if bit is set
def isBitSet(self, num, i):
    return (num >> i)  1
# Count set bits
def countSetBits(self, num):
    count = 0
    while num:
        count += num  1
        num >>= 1
    return count
# Count set bits (Brian Kernighan's algorithm)
def countSetBitsFast(self, num):
    count = 0
    while num:
        num = (num - 1)
        count += 1
    return count

Common Bit Tricks

# Get lowest set bit
def lowestSetBit(self, num):
    return num  (-num)
    # Clear lowest set bit
    def clearLowestSetBit(self, num):
        return num  (num - 1)
        # Check if power of 2
    def isPowerOfTwo(self, num):
        return num > 0  and  (num  (num - 1)) == 0
        # Get next power of 2
    def nextPowerOfTwo(self, num):
        num -= 1
        num |= num >> 1
        num |= num >> 2
        num |= num >> 4
        num |= num >> 8
        num |= num >> 16
        return num + 1
        # Swap two numbers
    def swap(self, a, 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)
def singleNumber(self, nums):
    result = 0
    for num in nums:
        result ^= num
    return result
# Single Number II (all appear three times except one)
def singleNumberII(self, nums):
    ones = 0, twos = 0
    for num in nums:
        ones = (ones ^ num)  ~twos
        twos = (twos ^ num)  ~ones
    return ones

Gray Code

def grayCode(self, n):
    list[int> result
    for (i = 0 i < (1 << n) i += 1) :
    result.append(i ^ (i >> 1))
return result
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 myPow(self, x, 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

# Greatest Common Divisor (Euclidean algorithm)
def gcd(self, a, b):
    while b != 0:
        temp = b
        b = a % b
        a = temp
    return a
# Recursive GCD
def gcdRecursive(self, a, b):
    (a if     return b == 0  else gcdRecursive(b, a % b))
# Least Common Multiple
def lcm(self, a, b):
    return a / gcd(a, b)  b

Prime Numbers

Check Prime

def isPrime(self, n):
    if (n < 2) return False
    if (n == 2) return True
    if (n % 2 == 0) return False
    for (i = 3 i  i <= n i += 2) :
    if (n % i == 0) return False
return True

Sieve of Eratosthenes

def sieveOfEratosthenes(self, n):
    list[bool> isPrime(n + 1, True)
    isPrime[0] = isPrime[1] = False
    for (i = 2 i  i <= n i += 1) :
    if isPrime[i]:
        for (j = i  i j <= n j += i) :
        isPrime[j] = False
return isPrime

Number Theory

Factorial Trailing Zeroes

def trailingZeroes(self, n):
    count = 0
    while n > 0:
        n /= 5
        count += n
        return count

Reverse Integer

def reverse(self, x):
    result = 0
    while x != 0:
        if result > INT_MAX / 10  or  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

More templates