Math & Bit Manipulation Exercises (with Solutions)
Time to practice. Solve each problem yourself first — write the code, trace a tiny example by hand, and reason about its time and space complexity. Only then open the answer sheet. Every View answer link jumps to a full, multi-language solution on the math & bit-manipulation solutions page.
How to practice: Set a timer (15–20 min per problem). Stuck? Re-read bit manipulation basics, common bit tricks, or modular arithmetic before peeking. The XOR and “power of two” problems are interview classics — make sure you can do them cold.
Warm-ups
Q1. Count set bits. Given a non-negative integer, return how many 1-bits are in its binary representation (its population count). Aim for O(number of set bits) rather than O(bit width).
Q2. Power of two. Given an integer n, return true if it is a power of two (1, 2, 4, 8, …) and false otherwise — including correct handling of 0 and negatives. Target O(1).
Core problems
Q3. Single number. Every element in an array appears exactly twice except for one, which appears once. Find that single element in O(n) time and O(1) extra space. Hint: think about a self-cancelling operator.
Q4. Missing number. An array contains n distinct numbers taken from the range 0..n (so exactly one value in that range is missing). Return the missing number in O(n) time and O(1) space.
Q5. Fast pow(x, n). Implement pow(x, n) (x raised to the integer power n) in O(log n) time, handling negative exponents. Do not call the language’s built-in power function.
Challenge
Q6. Count primes below n. Given an integer n, return how many prime numbers are strictly less than n. Aim for O(n log log n) using a sieve.
Q7. Add two integers without +. Compute the sum of two integers a and b without using the + or - operators — only bitwise operations. Hint: XOR is addition without carry; AND finds the carry.
Done? Review every solution on the math & bit-manipulation answer sheet — even the ones you solved, since there’s often a cleaner approach. Then continue to the advanced structures.