Bit Manipulation Tricks & Bitmasks

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Operating at the Silicon Bit Level

All computer data is stored in binary bits ($0$ and $1$). Bit Manipulation applies bitwise logic directly on integer bits in $O(1)$ instant execution time with zero memory overhead.

2. Core Bitwise Operators

3. High-Value Bit Manipulation Tricks

// Trick 1: Check if Number is Power of Two in O(1)
function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}
console.log(isPowerOfTwo(16)); // Output: true (16 is 10000_2, 15 is 01111_2 -> 16 & 15 == 0)
console.log(isPowerOfTwo(18)); // Output: false

// Trick 2: Find the Single Non-Duplicate Number using XOR
// Rule: x ^ x = 0 and x ^ 0 = x (Duplicates cancel out!)
function singleNumber(nums) {
  let result = 0;
  for (const num of nums) {
    result ^= num;
  }
  return result;
}
console.log(singleNumber([4, 1, 2, 1, 2])); // Output: 4 (1^1=0, 2^2=0 -> 4 remains)

// Trick 3: Count Set Bits (Hamming Weight / Brian Kernighan's Algorithm)
function countSetBits(n) {
  let count = 0;
  while (n > 0) {
    n &= (n - 1); // Clears the lowest set bit in O(1)
    count++;
  }
  return count;
}
console.log(countSetBits()); 

4. Bitmasks for State Representation

An integer can represent a set of up to 32 boolean flags:

• Set bit $i$: mask |= (1 << i)
• Clear bit $i$: mask &= ~(1 << i)
• Check bit $i$: (mask & (1 << i)) !== 0

5. Common Mistakes

• Operator Precedence Pitfall: In JavaScript, equality operators have higher precedence than bitwise operators! Writing n & 1 === 0 is evaluated as n & (1 === 0)! Always wrap bitwise operations in parentheses: (n & 1) === 0.

6. Congratulations!

Congratulations! You have completed all 30 foundational Data Structures & Algorithms Core Patterns Learning Bytes, mastering everything from Big O analysis, sliding windows, and linked lists to binary search trees, Dijkstra's algorithm, dynamic programming, and bit manipulation!