Bit Manipulation and Bitwise Operations

1. Bitmasking for Subset Enumeration

Concept Technique Formula/Pattern Use Case
Subset as Bitmask Represent subset using binary number bit i set → element i included Enumerate all 2n subsets
Iterate All Subsets Loop from 0 to 2n-1 for (let mask = 0; mask < (1<<n); mask++) Generate powerset efficiently
Check Bit Set Test if bit i is set in mask (mask >> i) & 1 or mask & (1<<i) Determine element membership
Set Bit Turn on bit i mask | (1 << i) Add element to subset
Clear Bit Turn off bit i mask & ~(1 << i) Remove element from subset
Toggle Bit Flip bit i mask ^ (1 << i) Add/remove element toggle

Example: Generate All Subsets Using Bitmask

function subsetsUsingBitmask(nums) {
  const n = nums.length;
  const result = [];
  
  // Iterate through all possible subsets (2^n)
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    
    // Check each bit position
    for (let i = 0; i < n; i++) {
      // If bit i is set, include nums[i]
      if ((mask >> i) & 1) {
        subset.push(nums[i]);
      }
    }
    
    result.push(subset);
  }
  
  return result;
}

console.log(subsetsUsingBitmask([1, 2, 3]));
// [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

// Mask representation:
// 000 (0) → []
// 001 (1) → [1]
// 010 (2) → [2]
// 011 (3) → [1,2]
// 100 (4) → [3]
// 101 (5) → [1,3]
// 110 (6) → [2,3]
// 111 (7) → [1,2,3]
Note: Bitmask subset enumeration is memory efficient (O(1) space for mask) and allows fast subset operations using bitwise operators. Perfect for problems with n ≤ 20 elements.

2. Generate All Subsets Using Bits

Operation Bitwise Formula Example Application
Count Subsets 2^n = 1 << n n=3 → 8 subsets Total number of subsets
Iterate Submasks for (s = mask; s; s = (s-1) & mask) Submasks of 101 → 101, 100, 001 Enumerate all submasks of mask
Power of 2 Check n & (n-1) === 0 8 (1000) & 7 (0111) = 0 Detect exact power of 2
Lowest Set Bit n & -n 12 (1100) → 4 (0100) Extract rightmost 1-bit
Remove Lowest Bit n & (n-1) 12 (1100) → 8 (1000) Clear rightmost 1-bit

Example: Iterate All Submasks of a Mask

function iterateSubmasks(mask) {
  const submasks = [];
  
  // Standard submask iteration trick
  for (let s = mask; s > 0; s = (s - 1) & mask) {
    submasks.push(s);
  }
  
  // Don't forget empty submask (0)
  submasks.push(0);
  
  return submasks;
}

console.log(iterateSubmasks(5)); // 5 = 101 in binary
// Output: [5, 4, 1, 0]
// 101 → 100 → 001 → 000

// Why this works:
// mask = 101
// s-1 flips all bits from rightmost 1
// & mask keeps only bits that are in original mask
// 101 - 1 = 100, 100 & 101 = 100
// 100 - 1 = 011, 011 & 101 = 001
// 001 - 1 = 000, 000 & 101 = 000 (loop ends)

Example: DP with Bitmask - Traveling Salesman Problem

function tsp(dist) {
  const n = dist.length;
  const VISITED_ALL = (1 << n) - 1;
  const dp = Array(1 << n).fill(null).map(() => Array(n).fill(Infinity));
  
  // Start from city 0
  dp[1][0] = 0;
  
  // Iterate all subsets
  for (let mask = 1; mask <= VISITED_ALL; mask++) {
    for (let last = 0; last < n; last++) {
      // If last city not in mask, skip
      if (!(mask & (1 << last))) continue;
      
      // Previous mask without last city
      const prevMask = mask ^ (1 << last);
      
      // Try all previous cities
      for (let prev = 0; prev < n; prev++) {
        if (prevMask & (1 << prev)) {
          dp[mask][last] = Math.min(
            dp[mask][last],
            dp[prevMask][prev] + dist[prev][last]
          );
        }
      }
    }
  }
  
  // Return to city 0 from any city
  let minCost = Infinity;
  for (let i = 1; i < n; i++) {
    minCost = Math.min(minCost, dp[VISITED_ALL][i] + dist[i][0]);
  }
  
  return minCost;
}

const dist = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0]
];
console.log(tsp(dist)); // 80

3. Counting Set Bits (Brian Kernighan's Algorithm)

Method Algorithm Time Description
Brian Kernighan n &= (n-1) in loop O(k) k=set bits Clears rightmost set bit each iteration
Naive Loop Check each bit with >> O(log n) Loop through all 32/64 bits
Built-in n.toString(2).split('1').length-1 O(log n) Convert to binary string and count '1's
Lookup Table Precompute counts for 0-255 O(1) Split number into bytes, lookup each
Parallel Count SWAR (SIMD Within A Register) O(1) Count bits in parallel using bit tricks

Example: Brian Kernighan's Algorithm

function countSetBits(n) {
  let count = 0;
  
  // Each iteration removes rightmost set bit
  while (n) {
    n &= (n - 1);
    count++;
  }
  
  return count;
}

console.log(countSetBits(13)); // 3 (1101 has 3 ones)
console.log(countSetBits(7));  // 3 (0111 has 3 ones)

// Trace for n=13 (1101):
// Iteration 1: 1101 & 1100 = 1100, count=1
// Iteration 2: 1100 & 1011 = 1000, count=2
// Iteration 3: 1000 & 0111 = 0000, count=3

// Why n & (n-1) removes rightmost set bit:
// n   = ...10110100
// n-1 = ...10110011  (flips bits after rightmost 1)
// &   = ...10110000  (rightmost 1 cleared)

Example: Count Bits for All Numbers 0 to n (DP)

function countBits(n) {
  const result = new Array(n + 1);
  result[0] = 0;
  
  for (let i = 1; i <= n; i++) {
    // Key insight: count[i] = count[i >> 1] + (i & 1)
    // Right shift removes last bit, &1 checks if last bit was 1
    result[i] = result[i >> 1] + (i & 1);
  }
  
  return result;
}

console.log(countBits(5)); 
// [0, 1, 1, 2, 1, 2]
// 0: 0000 → 0 bits
// 1: 0001 → 1 bit
// 2: 0010 → 1 bit
// 3: 0011 → 2 bits
// 4: 0100 → 1 bit
// 5: 0101 → 2 bits

// Alternative DP: result[i] = result[i & (i-1)] + 1
// i & (i-1) removes rightmost set bit
function countBitsAlt(n) {
  const result = new Array(n + 1);
  result[0] = 0;
  
  for (let i = 1; i <= n; i++) {
    result[i] = result[i & (i - 1)] + 1;
  }
  
  return result;
}

4. XOR Patterns (Single Number Problem)

Property Formula Example Application
Self XOR a ^ a = 0 5 ^ 5 = 0 Cancel out duplicates
XOR with 0 a ^ 0 = a 5 ^ 0 = 5 Identity property
Commutative a ^ b = b ^ a 3 ^ 5 = 5 ^ 3 Order doesn't matter
Associative (a ^ b) ^ c = a ^ (b ^ c) Can group any way Chain XOR operations
Find Unique result = a1 ^ a2 ^ ... ^ an All pairs cancel Find single non-duplicate
Swap Without Temp a^=b; b^=a; a^=b Swap two variables In-place swap

Example: Single Number - Find Unique Element

function singleNumber(nums) {
  let result = 0;
  
  // XOR all numbers: duplicates cancel out
  for (const num of nums) {
    result ^= num;
  }
  
  return result;
}

console.log(singleNumber([4, 1, 2, 1, 2])); // 4
// 0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2
// = 4 ^ (1 ^ 1) ^ (2 ^ 2)
// = 4 ^ 0 ^ 0
// = 4

Example: Single Number II - Element Appears Thrice

function singleNumberII(nums) {
  let ones = 0, twos = 0;
  
  for (const num of nums) {
    // Add to twos if already in ones
    twos |= ones & num;
    
    // XOR with ones
    ones ^= num;
    
    // Remove from both if appears 3 times
    const threes = ones & twos;
    ones &= ~threes;
    twos &= ~threes;
  }
  
  return ones;
}

console.log(singleNumberII([2, 2, 3, 2])); // 3
// All numbers appear 3 times except one

// Alternative using bit counting
function singleNumberIIBitCount(nums) {
  let result = 0;
  
  // Count bits at each position
  for (let i = 0; i < 32; i++) {
    let sum = 0;
    for (const num of nums) {
      sum += (num >> i) & 1;
    }
    
    // If count not divisible by 3, unique number has this bit
    if (sum % 3 !== 0) {
      result |= (1 << i);
    }
  }
  
  return result;
}

Example: Single Number III - Two Unique Elements

function singleNumberIII(nums) {
  // XOR all numbers: result = a ^ b (two unique numbers)
  let xorAll = 0;
  for (const num of nums) {
    xorAll ^= num;
  }
  
  // Find rightmost set bit (where a and b differ)
  const rightmostBit = xorAll & -xorAll;
  
  // Partition into two groups based on this bit
  let a = 0, b = 0;
  for (const num of nums) {
    if (num & rightmostBit) {
      a ^= num;
    } else {
      b ^= num;
    }
  }
  
  return [a, b];
}

console.log(singleNumberIII([1, 2, 1, 3, 2, 5])); // [3, 5]
// Step 1: 1^2^1^3^2^5 = 3^5 = 6 (110)
// Step 2: rightmost bit = 6 & -6 = 2 (010)
// Step 3: Partition by bit 1
//   Group 1 (bit set): 2,3,2 → 3
//   Group 2 (bit not set): 1,1,5 → 5

5. Bit Manipulation Tricks and Fast Operations

Operation Bit Trick Equivalent Use Case
Multiply by 2k n << k n * (2^k) Fast multiplication by power of 2
Divide by 2k n >> k Math.floor(n / (2^k)) Fast division by power of 2
Check Even/Odd n & 1 n % 2 0=even, 1=odd
Modulo Power of 2 n & (2^k - 1) n % (2^k) Fast modulo by power of 2
Absolute Value (n ^ (n >> 31)) - (n >> 31) Math.abs(n) Branchless absolute value
Min of Two b ^ ((a ^ b) & -(a < b)) Math.min(a, b) Branchless minimum
Max of Two a ^ ((a ^ b) & -(a < b)) Math.max(a, b) Branchless maximum
Sign Function (n >> 31) | ((-n) >>> 31) -1 if n<0, 0 if n=0, 1 if n>0 Get sign without branches
Next Power of 2 Decrease by 1, set all bits right of MSB, add 1 Find next 2k ≥ n Round up to power of 2
Isolate Rightmost 1 n & -n Get lowest set bit Extract least significant bit
Isolate Rightmost 0 ~n & (n+1) Get lowest unset bit Find first zero bit
Turn Off Rightmost 1 n & (n-1) Clear lowest set bit Remove least significant bit
Turn On Rightmost 0 n | (n+1) Set lowest unset bit Set first zero bit

Example: Common Bit Tricks

// Check if power of 2
function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

// Get next power of 2
function nextPowerOfTwo(n) {
  if (n <= 0) return 1;
  n--;
  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  n |= n >> 16;
  return n + 1;
}

// Swap two numbers without temp variable
function swap(a, b) {
  console.log(`Before: a=${a}, b=${b}`);
  a ^= b;
  b ^= a;
  a ^= b;
  console.log(`After: a=${a}, b=${b}`);
}

// Check if opposite signs
function oppositeSign(a, b) {
  return (a ^ b) < 0;
}

console.log(isPowerOfTwo(16)); // true
console.log(nextPowerOfTwo(10)); // 16
swap(5, 10); // Before: a=5, b=10, After: a=10, b=5
console.log(oppositeSign(5, -3)); // true
console.log(oppositeSign(5, 3)); // false

Example: Fast Modulo and Multiplication

function fastOperations() {
  const n = 25;
  
  // Multiply by 8 (2^3)
  console.log(n << 3); // 200 (same as n * 8)
  
  // Divide by 4 (2^2)
  console.log(n >> 2); // 6 (same as Math.floor(n / 4))
  
  // Check even/odd
  console.log(n & 1); // 1 (odd)
  console.log(24 & 1); // 0 (even)
  
  // Modulo 16 (2^4)
  console.log(n & 15); // 9 (same as n % 16, where 15 = 16-1)
  
  // Isolate rightmost set bit
  console.log(12 & -12); // 4 (1100 → 0100)
  
  // Remove rightmost set bit
  console.log(12 & 11); // 8 (1100 → 1000)
}

fastOperations();
Note: While bit tricks are fast, modern compilers often optimize standard operations automatically. Use bit tricks for clarity and specific algorithms (like counting bits, XOR problems), not general arithmetic unless profiling shows benefit.

6. Hamming Distance (Bit Difference Count)

Concept Definition Formula Application
Hamming Distance Number of positions where bits differ countBits(x ^ y) Measure bit difference between numbers
XOR for Difference XOR highlights different bits x ^ y gives 1 where bits differ Find positions of difference
Total Hamming Sum of all pairwise distances Count contribution of each bit position Analyze array bit differences
Hamming Weight Number of 1-bits in number countBits(n) Also called population count

Example: Hamming Distance Between Two Numbers

function hammingDistance(x, y) {
  // XOR to find differing bits, then count them
  let xor = x ^ y;
  let distance = 0;
  
  // Brian Kernighan's algorithm
  while (xor) {
    xor &= (xor - 1);
    distance++;
  }
  
  return distance;
}

console.log(hammingDistance(1, 4)); // 2
// 1 = 0001
// 4 = 0100
// XOR = 0101 (2 bits set)

Example: Total Hamming Distance of Array

function totalHammingDistance(nums) {
  let total = 0;
  const n = nums.length;
  
  // Check each bit position (0-31 for 32-bit integers)
  for (let bit = 0; bit < 32; bit++) {
    let countOnes = 0;
    
    // Count how many numbers have this bit set
    for (const num of nums) {
      if ((num >> bit) & 1) {
        countOnes++;
      }
    }
    
    // Numbers with 1 * numbers with 0 = pairs with different bit
    const countZeros = n - countOnes;
    total += countOnes * countZeros;
  }
  
  return total;
}

console.log(totalHammingDistance([4, 14, 2])); // 6
// 4  = 0100
// 14 = 1110
// 2  = 0010
//
// Bit 0: [0,0,0] → 0*3 = 0
// Bit 1: [0,1,1] → 1*2 = 2
// Bit 2: [1,1,1] → 3*0 = 0
// Bit 3: [0,1,0] → 1*2 = 2
// Total = 0+2+0+2+2 = 6

7. Check Power of Two Using Bits

Check Technique Why It Works Edge Cases
Is Power of 2 n > 0 && (n & (n-1)) === 0 Power of 2 has exactly one bit set n=0 is NOT power of 2
Count Check countBits(n) === 1 Exactly one 1-bit present Slower but more explicit
Is Power of 4 (n & (n-1)) === 0 && (n & 0x55555555) Power of 2 with bit at even position 0x55...5 = 01010101... pattern
Next Power of 2 Set all bits right of MSB, then add 1 Creates number like 2k-1, then +1 Handle n ≤ 0 specially

Example: Power of Two Variations

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

function isPowerOfFour(n) {
  // Must be power of 2 AND bit at even position (0,2,4,6,...)
  // 0x55555555 = 01010101010101010101010101010101 (bits at even positions)
  return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;
}

function nextPowerOfTwo(n) {
  if (n <= 1) return 1;
  
  // Decrease by 1 to handle exact powers of 2
  n--;
  
  // Set all bits to the right of MSB
  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  n |= n >> 16;
  
  // Add 1 to get next power of 2
  return n + 1;
}

console.log(isPowerOfTwo(16)); // true (10000)
console.log(isPowerOfTwo(18)); // false (10010)
console.log(isPowerOfFour(16)); // true (16 = 4^2)
console.log(isPowerOfFour(8)); // false (8 = 2^3, not 4^k)
console.log(nextPowerOfTwo(10)); // 16
console.log(nextPowerOfTwo(16)); // 16 (already power of 2)

Example: Find Missing Power of Two

function missingPowerOfTwo(arr, n) {
  // Array contains all powers of 2 from 2^0 to 2^n except one
  // Use XOR to find missing
  
  let xor = 0;
  
  // XOR all elements in array
  for (const num of arr) {
    xor ^= num;
  }
  
  // XOR all powers of 2 from 0 to n
  for (let i = 0; i <= n; i++) {
    xor ^= (1 << i);
  }
  
  return xor; // Missing number
}

// Array has [1,2,8,16,32] - missing 4
console.log(missingPowerOfTwo([1, 2, 8, 16, 32], 5)); // 4

8. Gray Code Generation Algorithm

Concept Property Formula Use Case
Gray Code Adjacent codes differ by exactly 1 bit gray = binary ^ (binary >> 1) Error correction, rotary encoders
Binary to Gray XOR with right-shifted version g = b ^ (b >> 1) Convert standard binary to Gray
Gray to Binary Accumulate XOR from MSB b ^= g >> i for all i Decode Gray code to binary
N-bit Gray Codes Recursive: reflect previous, prepend 0/1 2n unique codes Generate all n-bit Gray codes

Example: Generate Gray Code Sequence

function grayCode(n) {
  const result = [];
  const size = 1 << n; // 2^n
  
  for (let i = 0; i < size; i++) {
    // Convert binary i to Gray code
    result.push(i ^ (i >> 1));
  }
  
  return result;
}

console.log(grayCode(2)); // [0, 1, 3, 2]
// Binary: 00, 01, 10, 11
// Gray:   00, 01, 11, 10
//
// 0 ^ (0 >> 1) = 0 ^ 0 = 0 (00)
// 1 ^ (1 >> 1) = 1 ^ 0 = 1 (01)
// 2 ^ (2 >> 1) = 2 ^ 1 = 3 (11)
// 3 ^ (3 >> 1) = 3 ^ 1 = 2 (10)

console.log(grayCode(3)); // [0,1,3,2,6,7,5,4]
// Verify: each adjacent pair differs by 1 bit

Example: Gray Code Conversion

function binaryToGray(binary) {
  return binary ^ (binary >> 1);
}

function grayToBinary(gray) {
  let binary = gray;
  
  // XOR with all right-shifted versions
  while (gray >>= 1) {
    binary ^= gray;
  }
  
  return binary;
}

// Alternative: recursive reflection method
function grayCodeRecursive(n) {
  if (n === 0) return [0];
  if (n === 1) return [0, 1];
  
  // Get previous Gray codes
  const prev = grayCodeRecursive(n - 1);
  const result = [...prev];
  
  // Reflect and prepend 1 (add 2^(n-1))
  const prefix = 1 << (n - 1);
  for (let i = prev.length - 1; i >= 0; i--) {
    result.push(prefix | prev[i]);
  }
  
  return result;
}

console.log(binaryToGray(6)); // 5 (110 → 101)
console.log(grayToBinary(5)); // 6 (101 → 110)
console.log(grayCodeRecursive(3)); // [0,1,3,2,6,7,5,4]

9. Gosper's Hack (Next Combination with Same Set Bits)

Technique Purpose How It Works Complexity
Gosper's Hack Generate next k-combination in lexicographic order Find next number with same bit count O(1) per iteration
Pattern Iterate all n choose k combinations Maintains same number of set bits Total: O(C(n,k))
Formula c = x & -x; r = x + c; x = (((r^x)>>2)/c)|r Finds next combination efficiently Bitwise arithmetic only

Example: Gosper's Hack - Enumerate k-Combinations

function gospersHack(n, k) {
  const combinations = [];
  
  // Start with k rightmost bits set: 2^k - 1
  let set = (1 << k) - 1;
  const limit = 1 << n;
  
  while (set < limit) {
    combinations.push(set);
    
    // Gosper's hack: find next combination
    const c = set & -set; // Rightmost set bit
    const r = set + c; // Add to create carry
    set = (((r ^ set) >> 2) / c) | r;
  }
  
  return combinations;
}

// Get all 3-bit combinations from 5 bits
console.log(gospersHack(5, 3));
// [7, 11, 13, 14, 19, 21, 22, 25, 26, 28]
// Binary representations all have exactly 3 bits set:
// 00111 (7)
// 01011 (11)
// 01101 (13)
// 01110 (14)
// 10011 (19)
// ...

// Extract indices of set bits
function getIndices(mask) {
  const indices = [];
  let i = 0;
  while (mask) {
    if (mask & 1) indices.push(i);
    mask >>= 1;
    i++;
  }
  return indices;
}

const combs = gospersHack(5, 3);
console.log(combs.map(getIndices));
// [[0,1,2], [0,1,3], [0,2,3], [1,2,3], [0,1,4], ...]

Example: Apply Gosper's Hack to Array

function generateCombinations(arr, k) {
  const n = arr.length;
  const result = [];
  
  let set = (1 << k) - 1;
  const limit = 1 << n;
  
  while (set < limit) {
    const combination = [];
    
    // Extract elements based on set bits
    for (let i = 0; i < n; i++) {
      if ((set >> i) & 1) {
        combination.push(arr[i]);
      }
    }
    
    result.push(combination);
    
    // Next combination
    const c = set & -set;
    const r = set + c;
    set = (((r ^ set) >> 2) / c) | r;
  }
  
  return result;
}

console.log(generateCombinations(['a', 'b', 'c', 'd'], 2));
// [['a','b'], ['a','c'], ['b','c'], ['a','d'], ['b','d'], ['c','d']]

1. Bitmasking for Subset Enumeration

Operation Technique Steps Complexity
Reverse Bits Swap bits from outside to inside Swap 16-bit halves, 8-bit, 4-bit, 2-bit, 1-bit O(log n) bits
Swap Adjacent Bits Mask odd and even bits separately ((n & 0xAAAAAAAA)>>1)|((n & 0x55555555)<<1) O(1)
Swap Nibbles Swap 4-bit groups ((n & 0xF0F0F0F0)>>4)|((n & 0x0F0F0F0F)<<4) O(1)
Swap Bytes Swap 8-bit groups ((n & 0xFF00FF00)>>8)|((n & 0x00FF00FF)<<8) O(1)
Lookup Table Precompute reverse for 0-255 Split into bytes, lookup each, reassemble O(1)

Example: Reverse 32-bit Integer

function reverseBits(n) {
  // Swap 16-bit halves
  n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16);
  
  // Swap 8-bit halves within each 16-bit group
  n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8);
  
  // Swap 4-bit nibbles within each 8-bit group
  n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4);
  
  // Swap 2-bit pairs within each 4-bit group
  n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2);
  
  // Swap adjacent bits
  n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1);
  
  return n >>> 0; // Convert to unsigned
}

console.log(reverseBits(43261596).toString(2)); 
// Input:  00000010100101000001111010011100 (43261596)
// Output: 00111001011110000010100101000000 (964176192)

Example: Bit Reversal Variants

// Simple bit-by-bit reversal
function reverseBitsSimple(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result <<= 1;
    result |= (n & 1);
    n >>>= 1;
  }
  return result >>> 0;
}

// Swap adjacent bits
function swapAdjacentBits(n) {
  // 0xAAAAAAAA = 10101010... (odd positions)
  // 0x55555555 = 01010101... (even positions)
  return (((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1)) >>> 0;
}

// Swap nibbles (4-bit groups)
function swapNibbles(n) {
  // 0xF0F0F0F0 = high nibbles, 0x0F0F0F0F = low nibbles
  return (((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4)) >>> 0;
}

// Reverse byte order (big-endian ↔ little-endian)
function reverseBytes(n) {
  return (((n & 0xFF000000) >>> 24) |
          ((n & 0x00FF0000) >>> 8) |
          ((n & 0x0000FF00) << 8) |
          ((n & 0x000000FF) << 24)) >>> 0;
}

console.log(reverseBitsSimple(5)); // Same as reverseBits
console.log(swapAdjacentBits(0b10110100)); // 0b01101000
console.log(swapNibbles(0x12345678).toString(16)); // 0x21436587
console.log(reverseBytes(0x12345678).toString(16)); // 0x78563412
Note: Use >>> (unsigned right shift) instead of >> when working with bit reversal to avoid sign extension issues with negative numbers. The mask 0xAAAAAAAA = all odd bits, 0x55555555 = all even bits.

Summary: Bit Manipulation Pattern

  • Bitmasking: Use integers as sets - iterate 2n subsets with for (mask=0; mask<(1<<n); mask++)
  • Subset Generation: Powers of 2 are single bits; iterate submasks with s=(s-1)&mask
  • Counting Bits: Brian Kernighan's n&(n-1) removes rightmost bit - O(k) for k set bits
  • XOR Properties: a^a=0, a^0=a - perfect for finding unique elements in duplicates
  • Bit Tricks: n<<k = multiply by 2k, n>>k = divide by 2k, n&1 = check odd/even
  • Hamming Distance: Count bits in x^y - for arrays, count per bit position
  • Power of 2: Check with n>0 && (n&(n-1))===0 - exactly one bit set
  • Gray Code: binary^(binary>>1) - adjacent codes differ by 1 bit
  • Gosper's Hack: Generate next k-combination efficiently - maintains bit count
  • Reverse Bits: Swap progressively smaller chunks - 16-bit, 8-bit, 4-bit, 2-bit, 1-bit
  • Key Insight: Bits can represent sets, states, and choices - enables compact DP and combinatorial algorithms

Related Cheat Sheets

Algorithm Patterns

Backtracking Pattern

Datastructures Algorithms

Parallel and Concurrent Algorithms

Algorithm Patterns

Merge Intervals Pattern

Datastructures Algorithms

Mathematical Algorithms