Math & Bit Manipulation

Back to DSA & Algorithms/00 - Roadmap Overview

---

Bit Manipulation Fundamentals

Computers store numbers in binary. Bit manipulation operates directly on these binary representations — extremely fast (single CPU instruction).

Binary Refresher

Decimal 13 = Binary 1101

  8  4  2  1       (powers of 2)
  1  1  0  1       = 8 + 4 + 0 + 1 = 13

The Six Bitwise Operators

AND (&):  Both bits must be 1       1010 & 1100 = 1000
OR  (|):  At least one bit is 1     1010 | 1100 = 1110
XOR (^):  Bits must be different     1010 ^ 1100 = 0110
NOT (~):  Flip all bits              ~1010 = 0101 (in practice, also flips sign)
<<  :     Left shift (multiply by 2)  0101 << 1 = 1010
>>  :     Right shift (divide by 2)   1010 >> 1 = 0101

Essential Bit Tricks (Memorize These)

java
n & 1              // Is n odd? (check last bit)
n & (n - 1)        // Clear the lowest set bit
                   //   12 = 1100, 11 = 1011, 12 & 11 = 1000
                   //   Removed the rightmost 1!
n & (-n)           // Isolate the lowest set bit
                   //   12 = 1100, -12 = ...0100, 12 & -12 = 0100
n ^ n == 0         // XOR with itself = 0 (cancels out)
a ^ b ^ b == a     // XOR twice with same value = original
n << k             // Multiply by 2^k
n >> k             // Divide by 2^k (floor)
(1 << k)           // The number with only bit k set (= 2^k)
n | (1 << k)       // Set bit k
n & ~(1 << k)      // Clear bit k
(n >> k) & 1       // Get bit k (is it 0 or 1?)
Integer.bitCount(n)           // Count number of set bits
Integer.numberOfTrailingZeros(n)  // Index of lowest set bit

---

Pattern 1: XOR for Finding Unique Elements

The Key Property

XOR cancels pairs: a ^ a = 0 and a ^ 0 = a. If every number appears twice except one, XOR everything → the unique one remains.

java
// Every number appears twice except one. Find it.
public int singleNumber(int[] nums) {
    int result = 0;
    for (int n : nums) {
        result ^= n;
    }
    return result;
}

// [2, 1, 4, 1, 2]
// 0 ^ 2 = 2
// 2 ^ 1 = 3
// 3 ^ 4 = 7
// 7 ^ 1 = 6
// 6 ^ 2 = 4  ← the unique number!

// Why: 2^2 = 0, 1^1 = 0, leaving just 4.

Problems

• 136. Single Number - Easy
• 137. Single Number II - Medium
• 260. Single Number III - Medium

---

Pattern 2: Counting Bits

java
// Count the number of 1s in binary representation (Hamming weight)
public int countOnes(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);    // Clear lowest set bit
        count++;
    }
    return count;
    // Or simply: return Integer.bitCount(n);
}

// 13 = 1101, three 1s
// 1101 & 1100 = 1100 (cleared bit 0) → count=1
// 1100 & 1011 = 1000 (cleared bit 2) → count=2
// 1000 & 0111 = 0000 (cleared bit 3) → count=3, done

// Power of Two: exactly one bit set
public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}
// 8 = 1000, 7 = 0111, 8 & 7 = 0000 → true
// 6 = 0110, 5 = 0101, 6 & 5 = 0100 → false

Problems

• 191. Number of 1 Bits - Easy
• 338. Counting Bits - Easy
• 190. Reverse Bits - Easy
• 231. Power of Two - Easy
• 371. Sum of Two Integers - Medium

---

Pattern 3: Matrix Operations

Not bit manipulation, but math-heavy problems that appear frequently.

java
// Rotate Image 90° clockwise: Transpose + Reverse each row
public void rotate(int[][] matrix) {
    int n = matrix.length;
    // Transpose (swap rows and columns)
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // Reverse each row
    for (int[] row : matrix) {
        int left = 0, right = row.length - 1;
        while (left < right) {
            int temp = row[left];
            row[left] = row[right];
            row[right] = temp;
            left++;
            right--;
        }
    }
}

// Spiral Order
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++)    result.add(matrix[top][c]);
        top++;
        for (int r = top; r <= bottom; r++)    result.add(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--)  result.add(matrix[r][left]);
            left++;
        }
    }

    return result;
}

Problems

• 48. Rotate Image - Medium
• 73. Set Matrix Zeroes - Medium
• 54. Spiral Matrix - Medium
• 50. Pow(x, n) - Medium
• 7. Reverse Integer - Medium
• 202. Happy Number - Easy

---

Things to Be Aware Of

1. Java Integers Have Fixed Width

java
// Java int is 32-bit and long is 64-bit — overflow is possible.
// Unlike Python, Java does not have arbitrary precision integers.
// Always clarify with interviewer: "Should I handle 32-bit overflow?"
// Use long when intermediate results may exceed int range.

2. Negative Numbers in Binary

java
// Java uses two's complement for negative numbers.
// ~n = -(n + 1) in two's complement.
// For unsigned 32-bit behavior, use >>> (unsigned right shift)
// and mask with 0xFFFFFFFFL when needed.

3. XOR is Commutative and Associative

java
// Order doesn't matter: a ^ b ^ c = c ^ a ^ b
// This is why XOR finds the unique element regardless of array order.