Bit Manipulation: Mastering Binary Operations

Learn essential bitwise operations, tricks, and optimization techniques for competitive programming and low-level systems.

Bit Manipulation Usage (2023)

Compression (30%)

Cryptography (25%)

Networking (20%)

Graphics (15%)

Other (10%)

1. Bitwise Operations

Core Operators:

Operator	Symbol	Example	Result (5 & 3)
AND	&	0101 & 0011	0001 (1)
OR	\|	0101 \| 0011	0111 (7)
XOR	^	0101 ^ 0011	0110 (6)
NOT	~	~0101	1010 (-6)
Left Shift	<<	0101 << 1	1010 (10)
Right Shift	>>	0101 >> 1	0010 (2)

Common Operations:

Set Bit

function setBit(num, pos) {
  return num | (1 << pos);
}

Clear Bit

function clearBit(num, pos) {
  return num & ~(1 << pos);
}

Toggle Bit

function toggleBit(num, pos) {
  return num ^ (1 << pos);
}

Check Bit

function checkBit(num, pos) {
  return (num >> pos) & 1;
}

2. Advanced Techniques

Bit Hacks:

Power of Two Check

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

Count Set Bits

function countSetBits(num) {
  let count = 0;
  while (num > 0) {
    num &= num - 1;
    count++;
  }
  return count;
}

Swap Without Temp

function swap(a, b) {
  a ^= b;
  b ^= a;
  a ^= b;
  return [a, b];
}

Absolute Value

function abs(num) {
  const mask = num >> 31;
  return (num + mask) ^ mask;
}

Bitmask Applications:

Subset Generation

function subsets(nums) {
  const result = [];
  const n = nums.length;
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(nums[i]);
    }
    result.push(subset);
  }
  return result;
}

Prime Sieve

function sieve(max) {
  const isPrime = new Uint8Array((max >> 3) + 1).fill(0xFF);
  isPrime[0] &= ~3; // 0 and 1 not prime
  
  for (let p = 2; p * p <= max; p++) {
    if (isPrime[p >> 3] & (1 << (p & 7))) {
      for (let i = p * p; i <= max; i += p) {
        isPrime[i >> 3] &= ~(1 << (i & 7));
      }
    }
  }
  return isPrime;
}

3. Real-World Applications

Data Compression

Run-Length Encoding: Pack counts and values efficiently

function compressRLE(data) {
  let compressed = 0;
  let count = 1;
  for (let i = 1; i < data.length; i++) {
    if (data[i] === data[i-1] && count < 15) {
      count++;
    } else {
      compressed = (compressed << 4) | (count << 1) | data[i-1];
      count = 1;
    }
  }
  return compressed;
}

Network Protocols

TCP Flags: Single byte stores 8 boolean flags

class TCPHeader {
  constructor() {
    this.flags = 0; // URG|ACK|PSH|RST|SYN|FIN
  }
  
  setFlag(flagBit) {
    this.flags |= 1 << flagBit;
  }
  
  hasFlag(flagBit) {
    return this.flags & (1 << flagBit);
  }
}

Bit Manipulation Cheat Sheet

Operation	Formula	Example
Isolate Rightmost 1	x & (-x)	010100 → 000100
Clear Rightmost 1	x & (x - 1)	010100 → 010000
Propagate Rightmost 1	x \| (x - 1)	010100 → 010111
Swap Odd/Even Bits	((x & 0xAAAA) >> 1) \| ((x & 0x5555) << 1)	1010 1100 → 0101 1100

Bit Optimization Checklist

✓ Use bitmasks for multiple boolean flags

✓ Prefer bitshifts over multiplication/division by powers of 2

✓ Consider XOR for toggle operations

✓ Use AND with 1 to check odd/even

✓ Memorize common bit hacks

Pro Tip: In JavaScript, use typed arrays (Uint8Array, etc.) for memory-efficient bit storage. For large-scale operations, consider WebAssembly for near-native bit manipulation performance.

0 Interaction

0 Views

0 Likes