Category 12

Bit Manipulation & Math

Master low-level bit operations, mathematical algorithms, and optimization techniques. Learn XOR properties, bit shifting patterns, fast exponentiation, number theory foundations, and how to detect overflow and optimize numeric computations.

10
Problems
3
Difficulty Levels
100%
Complete Solutions
3
Codility Problems
Theory

Bit Manipulation & Mathematical Foundations

Bit operations form the foundation of hardware-level optimizations and elegant algorithm designs. Understanding XOR, bit shifting, and mathematical properties enables fast, elegant solutions to many problems.

1. XOR Properties

Key identities: a ^ a = 0, a ^ 0 = a, a ^ b = b ^ a (commutative), (a ^ b) ^ c = a ^ (b ^ c) (associative).

Application: XOR all elements to find the single unpaired element, since duplicate pairs cancel out (n ^ n = 0). Works even with negative numbers.

2. Bit Counting & Manipulation

Brian Kernighan's algorithm: n & (n-1) turns off the rightmost 1-bit. Loop until n = 0 to count set bits in O(popcount) time instead of O(log n).

n & (n-1) == 0: True only if n is a power of two (exactly one bit set).

3. Fast Exponentiation

Compute a^b in O(log b) using binary exponentiation. Square the base and divide exponent by 2 at each step. Apply modular arithmetic to prevent overflow.

4. Sieve of Eratosthenes

Efficiently find all primes up to n in O(n log log n) time. Mark multiples of each discovered prime as composite. Use a boolean array for space efficiency.

5. Number Theory Basics

GCD: Use Euclidean algorithm: gcd(a, b) = gcd(b, a mod b). Modular arithmetic: (a × b) mod m = ((a mod m) × (b mod m)) mod m. Essential for preventing overflow in large computations.

Problems
1. Single Number (LC 136)

Given a non-empty array where every element appears twice except one, find the single element. Use XOR's cancellation property to eliminate pairs efficiently.

Easy Bit Manipulation O(n) Time
1
Input
[4, 1, 2, 1, 2]
Output
4
Time
O(n)
Space
O(1)

Approach

1
Initialize result to 0. XOR-ing with 0 leaves value unchanged.
2
Iterate through each element. XOR it with result: result ^= nums[i].
3
Return result. Duplicate pairs cancel (a ^ a = 0), leaving only the single element.

Code Solution (C#)

csharp 
public int SingleNumber(int[] nums) {
    int result = 0;
    foreach (int num in nums) {
        result ^= num;
    }
    return result;
}

Trace Example

trace 
nums = [4, 1, 2, 1, 2]
result = 0

i=0: result = 0 ^ 4 = 4
i=1: result = 4 ^ 1 = 5
i=2: result = 5 ^ 2 = 7
i=3: result = 7 ^ 1 = 6 (1 ^ 1 = 0, so effect on bits)
i=4: result = 6 ^ 2 = 4

Binary check:
4 = 0100, 1 = 0001, 2 = 0010
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4 ✓
💡
Why XOR works: XOR is bitwise commutative and associative. Each bit position is evaluated independently. For a bit position, XOR of even 0s and 1s in pairs cancels out; odd 1 leaves the single element's bit.

Edge Cases

Case Input Output Note
Single element [5] 5 0 ^ 5 = 5
Negative number [-2, 1, -2, 1, 4] 4 XOR works on two's complement
Large range [int.MaxValue, 1, int.MaxValue] 1 No overflow with XOR

Complexity

Time: O(n) — single pass through array. Space: O(1) — only integer variable used.

2. Number of 1 Bits (LC 191)

Count the number of 1-bits in the binary representation of an unsigned integer using Brian Kernighan's algorithm.

Easy Bit Manipulation O(popcount)
2
Input
11 (0b1011)
Output
3
Time
O(k)
Space
O(1)

Approach

Brian Kernighan's trick: n & (n-1) removes the rightmost 1-bit. Repeat until n becomes 0. Count iterations.

Code Solution (C#)

csharp 
public int HammingWeight(uint n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;  // Remove rightmost 1-bit
        count++;
    }
    return count;
}

Trace Example

trace 
n = 11 = 0b1011
count = 0

Iteration 1: n = 1011, n-1 = 1010, n &= (n-1) → 1010, count = 1
Iteration 2: n = 1010, n-1 = 1001, n &= (n-1) → 1000, count = 2
Iteration 3: n = 1000, n-1 = 0111, n &= (n-1) → 0000, count = 3
n == 0, stop

Result: 3 ✓
💡
Why efficient: Time complexity is O(k) where k is the count of 1-bits, not O(log n). If sparse, very fast. Regular bit-shift approach is O(32) for uint.

Edge Cases

Input Binary Output
0 0b0000 0
1 0b0001 1
uint.MaxValue 32 ones 32

Complexity

Time: O(k) where k = popcount (number of 1-bits). Space: O(1).

3. Counting Bits (LC 338)

Given an integer n, return an array of bit counts: ans[i] = count of 1-bits in i for each i from 0 to n.

Easy Dynamic Programming O(n)
3
Input
5
Output
[0,1,1,2,1,2]
Time
O(n)
Space
O(n)

Approach

DP recurrence: ans[i] = ans[i >> 1] + (i & 1). Right shift removes rightmost bit (divide by 2), so bit count of i = bit count of i/2 plus the LSB.

Code Solution (C#)

csharp 
public int[] CountBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}

Trace Example

trace 
n = 5
ans = [0, 0, 0, 0, 0, 0]

i=1: 1 >> 1 = 0, 1 & 1 = 1, ans[1] = ans[0] + 1 = 1
i=2: 2 >> 1 = 1, 2 & 1 = 0, ans[2] = ans[1] + 0 = 1
i=3: 3 >> 1 = 1, 3 & 1 = 1, ans[3] = ans[1] + 1 = 2
i=4: 4 >> 1 = 2, 4 & 1 = 0, ans[4] = ans[2] + 0 = 1
i=5: 5 >> 1 = 2, 5 & 1 = 1, ans[5] = ans[2] + 1 = 2

Result: [0, 1, 1, 2, 1, 2] ✓

Edge Cases

n Output Pattern
0 [0] Single element
1 [0,1] Powers of 2
7 [0,1,1,2,1,2,2,3] Full byte

Complexity

Time: O(n) — single pass, O(1) per element. Space: O(n) for output array.

4. Power of Two (LC 231)

Given an integer n, return true if it is a power of two. Use the bit manipulation trick: power of two has exactly one bit set.

Easy Bit Manipulation O(1)
4
Input
16
Output
true
Time
O(1)
Space
O(1)

Approach

Key insight: Powers of 2 have exactly one bit set (e.g., 8 = 0b1000). Check if n & (n-1) == 0 and n > 0. If true, n is a power of 2.

Code Solution (C#)

csharp 
public bool IsPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Trace Example

trace 
n = 16 = 0b10000
n-1 = 15 = 0b01111
n & (n-1) = 0b10000 & 0b01111 = 0b00000 = 0 ✓
Result: true (16 = 2^4)

n = 6 = 0b00110
n-1 = 5 = 0b00101
n & (n-1) = 0b00110 & 0b00101 = 0b00100 ≠ 0
Result: false (6 is not a power of 2)

Edge Cases

Input Output Note
1 true 2^0 = 1
0 false Filtered by n > 0
-16 false Negative filtered
1024 true 2^10

Complexity

Time: O(1) — constant bitwise operations. Space: O(1).

5. Reverse Bits (LC 190)

Reverse the bits of a given 32-bit unsigned integer and return the reversed value.

Easy Bit Manipulation O(1)
5
Input
43261596
Output
964176192
Time
O(1)
Space
O(1)

Approach

Shift and build: Extract the LSB using n & 1, shift left into result, then right-shift n. Repeat 32 times.

Code Solution (C#)

csharp 
public uint ReverseBits(uint n) {
    uint result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}

Trace Example

trace 
n = 0b00000010100101000001111010110100 (43261596)

Extract and reverse (first 8 bits shown):
i=0: bit=0, result=0, n >>= 1
i=1: bit=0, result=0, n >>= 1
...continuing pattern...
Result = 0b00111001011110000010100101000010 (964176192) ✓

Edge Cases

Input (Binary) Output (Binary) Note
0b1 (1) 0b10000...0 (2^31) Single bit reverses to position 31
0 (0) 0 (0) Palindrome
uint.MaxValue uint.MaxValue All 1s palindrome

Complexity

Time: O(1) — fixed 32 iterations. Space: O(1).

6. Missing Number (LC 268)

Given an array of n numbers from 0 to n (with one missing), find the missing one. Use XOR or math approach.

Easy Bit Manipulation / Math O(n)
6
Input
[3,0,1]
Output
2
Time
O(n)
Space
O(1)

Approach (XOR Method)

XOR all array elements with all numbers 0 to n. Duplicates cancel out, leaving the missing number.

Code Solution (C#)

csharp 
public int MissingNumber(int[] nums) {
    int result = nums.Length;  // Start with n
    for (int i = 0; i < nums.Length; i++) {
        result ^= i ^ nums[i];
    }
    return result;
}

Trace Example

trace 
nums = [3, 0, 1], n = 3
result = 3

i=0: result = 3 ^ 0 ^ 3 = 0
i=1: result = 0 ^ 1 ^ 0 = 1
i=2: result = 1 ^ 2 ^ 1 = 2

Final: result = 2 ✓ (missing from [0,1,2,3])

Edge Cases

Input Output Note
[0] 1 Missing is n
[1] 0 Missing is 0
[0,1,2,3,4,5,6,7,8] 9 Missing is n

Complexity

Time: O(n) — single pass. Space: O(1).

7. Pow(x, n) (LC 50)

Implement x^n efficiently using fast exponentiation (binary exponentiation). Handle negative exponents and overflow cases.

Medium Math / Bit Manipulation O(log n)
7
Input
x=2.0, n=10
Output
1024.0
Time
O(log n)
Space
O(1)

Approach

Binary exponentiation: Decompose n using binary representation. If bit i is set, multiply result by x^(2^i). Use iterative approach to avoid recursion overhead.

Code Solution (C#)

csharp 
public double MyPow(double x, int n) {
    long N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }

    double result = 1.0;
    double base_val = x;

    while (N > 0) {
        if (N % 2 == 1) {
            result *= base_val;
        }
        base_val *= base_val;
        N /= 2;
    }

    return result;
}

Trace Example

trace 
x = 2.0, n = 10 = 0b1010
result = 1.0, base_val = 2.0

N=10: N%2=0, base_val = 4.0, N = 5
N=5: N%2=1, result = 4.0, base_val = 16.0, N = 2
N=2: N%2=0, base_val = 256.0, N = 1
N=1: N%2=1, result = 4.0 * 256.0 = 1024.0, base_val = (not used), N = 0

Result: 1024.0 ✓

Edge Cases

x n Output Note
2.0 -2147483648 ≈0 Negative overflow; use long
1.0 Any 1.0 1 to any power is 1
-1.0 Odd/Even ±1 Check parity

Complexity

Time: O(log n) — process each binary digit. Space: O(1).

8. Count Primes (LC 204)

Count the number of primes less than n using the Sieve of Eratosthenes algorithm.

Medium Number Theory O(n log log n)
8
Input
10
Output
4
Time
O(n log log n)
Space
O(n)

Approach

Sieve of Eratosthenes: Create boolean array, mark 0 and 1 as non-prime. For each prime p, mark all multiples 2p, 3p, 4p... as non-prime. Count remaining unmarked numbers.

Code Solution (C#)

csharp 
public int CountPrimes(int n) {
    if (n <= 2) return 0;

    bool[] is_prime = new bool[n];
    for (int i = 2; i < n; i++) {
        is_prime[i] = true;
    }

    for (int i = 2; i * i < n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    int count = 0;
    for (int i = 2; i < n; i++) {
        if (is_prime[i]) count++;
    }
    return count;
}

Trace Example

trace 
n = 10
is_prime = [F, F, T, T, T, T, T, T, T, T] (index 0-9)

i=2: Mark multiples starting from 4: 4,6,8 → [F,F,T,T,F,T,F,T,F,T]
i=3: Mark multiples starting from 9: 9 → [F,F,T,T,F,T,F,T,F,F]
i≥4: 4*4=16 ≥ 10, stop

Primes: 2, 3, 5, 7 → count = 4 ✓

Edge Cases

n Output Primes
0 0 None
2 0 None (less than 2)
3 1 2
100 25 2, 3, 5, ..., 97

Complexity

Time: O(n log log n) — sieve efficiency. Space: O(n) for boolean array.

9. FrogJmp (Codility)

A frog must jump from position X to position Y in steps of D. Count minimum jumps needed using ceiling division.

Easy Math O(1)
9
Input
X=10, Y=85, D=30
Output
3
Time
O(1)
Space
O(1)

Approach

Ceiling division: Number of jumps = ceil((Y - X) / D) = (Y - X + D - 1) / D using integer division.

Code Solution (C#)

csharp 
public int FrogJmp(int X, int Y, int D) {
    return (Y - X + D - 1) / D;
}

Trace Example

trace 
X=10, Y=85, D=30
distance = Y - X = 85 - 10 = 75

jumps = (75 + 30 - 1) / 30 = 104 / 30 = 3 ✓

Verify:
- After jump 1: 10 + 30 = 40
- After jump 2: 40 + 30 = 70
- After jump 3: 70 + 30 = 100 ≥ 85 ✓

Edge Cases

X Y D Output
1 5 2 2
1 5 4 1
0 1000000000 1 1000000000

Complexity

Time: O(1) — arithmetic only. Space: O(1).

10. CountNonDivisible (Codility)

Count how many elements in the array are NOT divisors of each element.

Hard Number Theory / Optimization O(n √m)
10
Input
[3, 1, 2, 3, 6]
Output
[2, 4, 3, 2, 0]
Time
O(n √m)
Space
O(m)

Approach

Key insight: For each element A[i], count divisors efficiently. Find all divisors of A[i] by checking up to √A[i]. Use frequency map to avoid redundant factor counting.

Code Solution (C#)

csharp 
public int[] CountNonDivisible(int[] A) {
    Dictionary<int, int> freq = new Dictionary<int, int>();
    int maxVal = 0;

    foreach (int x in A) {
        if (freq.ContainsKey(x)) freq[x]++;
        else freq[x] = 1;
        maxVal = Math.Max(maxVal, x);
    }

    int[] result = new int[A.Length];

    for (int i = 0; i < A.Length; i++) {
        int divisorCount = 0;

        for (int d = 1; d * d <= A[i]; d++) {
            if (A[i] % d == 0) {
                if (freq.ContainsKey(d)) divisorCount += freq[d];

                int other = A[i] / d;
                if (other != d && freq.ContainsKey(other)) {
                    divisorCount += freq[other];
                }
            }
        }

        result[i] = A.Length - divisorCount;
    }

    return result;
}

Trace Example

trace 
A = [3, 1, 2, 3, 6]
freq = {3:2, 1:1, 2:1, 6:1}

i=0: A[0]=3
  d=1: 3%1=0, freq[1]=1, other=3, freq[3]=2 → divisorCount=3
  result[0] = 5-3 = 2 ✓

i=1: A[1]=1
  d=1: 1%1=0, freq[1]=1, other=1 (skip) → divisorCount=1
  result[1] = 5-1 = 4 ✓

i=2: A[2]=2
  d=1: 2%1=0, freq[1]=1, other=2, freq[2]=1 → divisorCount=2
  result[2] = 5-2 = 3 ✓

i=3: A[3]=3
  Same as i=0: result[3] = 2 ✓

i=4: A[4]=6
  d=1: 6%1=0, freq[1]=1, other=6, freq[6]=1 → divisorCount=2
  d=2: 6%2=0, freq[2]=1, other=3, freq[3]=2 → divisorCount=2+1+2=5
  result[4] = 5-5 = 0 ✓

Result: [2, 4, 3, 2, 0] ✓
💡
Optimization key: Find divisors up to √n instead of checking all n. For each d dividing n, both d and n/d are divisors. Avoid double-counting when d = √n.

Edge Cases

Input Output Note
[1] [0] 1 divides itself
[2, 2] [1, 1] Duplicates handled
[12, 8] [1, 1] Factors: 1,2,3,4,6,12 for 12

Complexity

Time: O(n√m) where m is max element. For each element, find divisors in O(√m). Space: O(m) for frequency map.