Contents

Bit Operations

Basic Operations

// Set bit at position i
int setBit(int num, int i) {
    return num | (1 << i);
}

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

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

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

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

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

Common Bit Tricks

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

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

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

// Get next power of 2
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
void swap(int& a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}
ID Title 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)
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

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

Gray Code

vector<int> grayCode(int n) {
    vector<int> result;
    for (int i = 0; i < (1 << n); ++i) {
        result.push_back(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
double myPow(double x, int 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)
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

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

// Least Common Multiple
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

Prime Numbers

Check Prime

bool 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

vector<bool> sieveOfEratosthenes(int n) {
    vector<bool> 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

int trailingZeroes(int n) {
    int count = 0;
    while (n > 0) {
        n /= 5;
        count += n;
    }
    return count;
}

Reverse Integer

int reverse(int x) {
    int result = 0;
    while (x != 0) {
        if (result > INT_MAX / 10 || 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