Bit Manipulation - Complete Guide

Bit manipulation uses bitwise operators to solve problems efficiently. This guide covers essential bit manipulation techniques and common problems.

Binary Basics #

Binary Representation #

const num = 5;

// Convert to binary string
console.log(num.toString(2));  // "101"

// Parse binary string
console.log(parseInt('101', 2));  // 5

// Binary representation
// 5 = 0000 0101 (8-bit)
//     128 64 32 16 8 4 2 1
//       0  0  0  0 0 1 0 1

Signed Integers #

// Positive: 5 = 0000 0101
// Negative: -5 = 1111 1011 (two's complement)

// Two's complement:
// 1. Flip all bits: 0000 0101 → 1111 1010
// 2. Add 1:         1111 1010 → 1111 1011

Bitwise Operators #

AND (&) #

Both bits must be 1.

const a = 5;  // 0101
const b = 3;  // 0011
const c = a & b;  // 0001 = 1

console.log(c);  // 1

// Common use: Check if bit is set
function isBitSet(num, bit) {
  return (num & (1 << bit)) !== 0;
}

console.log(isBitSet(5, 0));  // true (bit 0 is set)
console.log(isBitSet(5, 1));  // false (bit 1 is not set)
console.log(isBitSet(5, 2));  // true (bit 2 is set)

OR (|) #

At least one bit must be 1.

const a = 5;  // 0101
const b = 3;  // 0011
const c = a | b;  // 0111 = 7

console.log(c);  // 7

// Common use: Set bit
function setBit(num, bit) {
  return num | (1 << bit);
}

console.log(setBit(5, 1));  // 7 (5 = 0101 → 0111 = 7)

XOR (^) #

Bits must be different.

const a = 5;  // 0101
const b = 3;  // 0011
const c = a ^ b;  // 0110 = 6

console.log(c);  // 6

// Properties:
// x ^ 0 = x
// x ^ x = 0
// x ^ y ^ x = y

// Common use: Toggle bit
function toggleBit(num, bit) {
  return num ^ (1 << bit);
}

console.log(toggleBit(5, 1));  // 7 (0101 → 0111)
console.log(toggleBit(7, 1));  // 5 (0111 → 0101)

NOT (~) #

Flips all bits.

const a = 5;  // 0000 0101
const b = ~a;  // 1111 1010 = -6

console.log(b);  // -6

// ~n = -(n + 1)

Left Shift («) #

Shift bits left, fill with 0s.

const a = 5;  // 0000 0101
const b = a << 1;  // 0000 1010 = 10

console.log(b);  // 10

// Left shift by n = multiply by 2^n
console.log(5 << 1);  // 10 (5 * 2)
console.log(5 << 2);  // 20 (5 * 4)
console.log(5 << 3);  // 40 (5 * 8)

Right Shift (») #

Shift bits right, preserve sign.

const a = 10;  // 0000 1010
const b = a >> 1;  // 0000 0101 = 5

console.log(b);  // 5

// Right shift by n = divide by 2^n (floor)
console.log(10 >> 1);  // 5 (10 / 2)
console.log(10 >> 2);  // 2 (10 / 4)

// Negative numbers
console.log(-10 >> 1);  // -5 (preserves sign)

Unsigned Right Shift (»>) #

Shift bits right, fill with 0s.

const a = -10;
const b = a >>> 1;

console.log(a >> 1);   // -5 (sign preserved)
console.log(a >>> 1);  // 2147483643 (unsigned)

Common Bit Operations #

Check if Power of 2 #

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

console.log(isPowerOfTwo(4));   // true (100 & 011 = 000)
console.log(isPowerOfTwo(16));  // true
console.log(isPowerOfTwo(6));   // false (110 & 101 = 100)

Count Set Bits #

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

console.log(countSetBits(7));   // 3 (111)
console.log(countSetBits(15));  // 4 (1111)

// Brian Kernighan's algorithm
function countSetBitsFast(n) {
  let count = 0;
  while (n > 0) {
    n &= (n - 1);  // Remove rightmost set bit
    count++;
  }
  return count;
}

Clear Rightmost Set Bit #

function clearRightmostBit(n) {
  return n & (n - 1);
}

console.log(clearRightmostBit(10));  // 8 (1010 → 1000)
console.log(clearRightmostBit(7));   // 6 (111 → 110)

Get Rightmost Set Bit #

function getRightmostBit(n) {
  return n & -n;
}

console.log(getRightmostBit(10));  // 2 (1010 → 0010)
console.log(getRightmostBit(12));  // 4 (1100 → 0100)

Check if Bit is Set #

function isBitSet(num, bit) {
  return (num & (1 << bit)) !== 0;
}

console.log(isBitSet(5, 0));  // true (0101, bit 0)
console.log(isBitSet(5, 1));  // false (0101, bit 1)

Set Bit #

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

console.log(setBit(5, 1));  // 7 (0101 → 0111)

Clear Bit #

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

console.log(clearBit(7, 1));  // 5 (0111 → 0101)

Toggle Bit #

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

console.log(toggleBit(5, 1));  // 7 (0101 → 0111)
console.log(toggleBit(7, 1));  // 5 (0111 → 0101)

Classic Problems #

Single Number #

Find the number that appears once while others appear twice.

function singleNumber(nums) {
  let result = 0;
  for (const num of nums) {
    result ^= num;  // XOR cancels out pairs
  }
  return result;
}

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

Missing Number #

Find missing number in array 0 to n.

function missingNumber(nums) {
  let missing = nums.length;
  for (let i = 0; i < nums.length; i++) {
    missing ^= i ^ nums[i];
  }
  return missing;
}

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

Reverse Bits #

function reverseBits(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result <<= 1;           // Make room
    result |= (n & 1);      // Add bit
    n >>= 1;                // Move to next bit
  }
  return result >>> 0;  // Convert to unsigned
}

console.log(reverseBits(43261596));  // 964176192

Number of 1 Bits (Hamming Weight) #

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= (n - 1);
    count++;
  }
  return count;
}

console.log(hammingWeight(11));  // 3 (1011)

Power of Four #

function isPowerOfFour(n) {
  // Must be power of 2 and only set bit at even position
  return n > 0 &&
         (n & (n - 1)) === 0 &&
         (n & 0x55555555) !== 0;
}

console.log(isPowerOfFour(16));  // true
console.log(isPowerOfFour(8));   // false

Counting Bits #

Count set bits for 0 to n.

function countBits(n) {
  const result = new Array(n + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    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)

Sum of Two Integers #

Add without using + operator.

function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}

console.log(getSum(1, 2));   // 3
console.log(getSum(5, 7));   // 12

Bitwise AND of Range #

function rangeBitwiseAnd(left, right) {
  let shift = 0;
  while (left !== right) {
    left >>= 1;
    right >>= 1;
    shift++;
  }
  return left << shift;
}

console.log(rangeBitwiseAnd(5, 7));   // 4
console.log(rangeBitwiseAnd(0, 0));   // 0
console.log(rangeBitwiseAnd(1, 2147483647));  // 0

Bit Manipulation Tricks #

Swap Without Temp #

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

console.log(swap(5, 10));  // [10, 5]

Get Absolute Value #

function abs(n) {
  const mask = n >> 31;  // All 1s if negative, all 0s if positive
  return (n + mask) ^ mask;
}

console.log(abs(-5));   // 5
console.log(abs(5));    // 5

Min/Max Without Branching #

function min(a, b) {
  return b ^ ((a ^ b) & -(a < b));
}

function max(a, b) {
  return a ^ ((a ^ b) & -(a < b));
}

console.log(min(5, 10));  // 5
console.log(max(5, 10));  // 10

Check Opposite Signs #

function oppositeSign(a, b) {
  return (a ^ b) < 0;
}

console.log(oppositeSign(5, -10));   // true
console.log(oppositeSign(5, 10));    // false

Turn Off Last Consecutive 1s #

function turnOffConsecutiveOnes(n) {
  return n & (n + 1);
}

console.log(turnOffConsecutiveOnes(7));   // 0 (111 → 000)
console.log(turnOffConsecutiveOnes(15));  // 0 (1111 → 0000)

Check if All Bits Set #

function areAllBitsSet(n) {
  return (n & (n + 1)) === 0;
}

console.log(areAllBitsSet(7));   // true (111)
console.log(areAllBitsSet(15));  // true (1111)
console.log(areAllBitsSet(10));  // false (1010)

Bit Masking #

Extract Bits #

function extractBits(num, i, j) {
  // Extract bits from position i to j
  const mask = ((1 << (j - i + 1)) - 1) << i;
  return (num & mask) >> i;
}

console.log(extractBits(171, 2, 5));
// 171 = 10101011
// Extract bits 2-5: 1010

Set Range of Bits #

function setBits(num, i, j, value) {
  const allOnes = ~0;
  const left = allOnes << (j + 1);
  const right = (1 << i) - 1;
  const mask = left | right;

  return (num & mask) | (value << i);
}

console.log(setBits(0b10000000, 2, 5, 0b1010));
// Set bits 2-5 to 1010

Advanced Problems #

Gray Code #

function grayCode(n) {
  const result = [];
  const total = 1 << n;

  for (let i = 0; i < total; i++) {
    result.push(i ^ (i >> 1));
  }

  return result;
}

console.log(grayCode(2));  // [0, 1, 3, 2]
console.log(grayCode(3));  // [0, 1, 3, 2, 6, 7, 5, 4]

Maximum XOR #

function findMaximumXOR(nums) {
  let max = 0;
  let mask = 0;

  for (let i = 31; i >= 0; i--) {
    mask |= (1 << i);
    const prefixes = new Set();

    for (const num of nums) {
      prefixes.add(num & mask);
    }

    const candidate = max | (1 << i);

    for (const prefix of prefixes) {
      if (prefixes.has(prefix ^ candidate)) {
        max = candidate;
        break;
      }
    }
  }

  return max;
}

console.log(findMaximumXOR([3, 10, 5, 25, 2, 8]));  // 28

Divide Two Integers #

function divide(dividend, divisor) {
  if (dividend === -2147483648 && divisor === -1) {
    return 2147483647;
  }

  const negative = (dividend < 0) !== (divisor < 0);
  dividend = Math.abs(dividend);
  divisor = Math.abs(divisor);

  let result = 0;

  while (dividend >= divisor) {
    let temp = divisor;
    let multiple = 1;

    while (dividend >= (temp << 1)) {
      temp <<= 1;
      multiple <<= 1;
    }

    dividend -= temp;
    result += multiple;
  }

  return negative ? -result : result;
}

console.log(divide(10, 3));   // 3
console.log(divide(7, -3));   // -2

Practical Applications #

Flags/Permissions #

const READ = 1 << 0;    // 0001
const WRITE = 1 << 1;   // 0010
const EXECUTE = 1 << 2; // 0100

function hasPermission(permissions, flag) {
  return (permissions & flag) !== 0;
}

function grantPermission(permissions, flag) {
  return permissions | flag;
}

function revokePermission(permissions, flag) {
  return permissions & ~flag;
}

let permissions = READ | WRITE;  // 0011

console.log(hasPermission(permissions, READ));     // true
console.log(hasPermission(permissions, EXECUTE));  // false

permissions = grantPermission(permissions, EXECUTE);  // 0111
console.log(hasPermission(permissions, EXECUTE));     // true

permissions = revokePermission(permissions, WRITE);   // 0101
console.log(hasPermission(permissions, WRITE));       // false

Set Operations #

class BitSet {
  constructor(size) {
    this.bits = new Array(Math.ceil(size / 32)).fill(0);
  }

  set(index) {
    const bucket = Math.floor(index / 32);
    const position = index % 32;
    this.bits[bucket] |= (1 << position);
  }

  clear(index) {
    const bucket = Math.floor(index / 32);
    const position = index % 32;
    this.bits[bucket] &= ~(1 << position);
  }

  has(index) {
    const bucket = Math.floor(index / 32);
    const position = index % 32;
    return (this.bits[bucket] & (1 << position)) !== 0;
  }
}

const set = new BitSet(100);
set.set(5);
set.set(50);
console.log(set.has(5));   // true
console.log(set.has(10));  // false

Best Practices #

  1. Use clear operations - Name helper functions
  2. Comment bit tricks - Not always obvious
  3. Test edge cases - Zero, negative, max values
  4. Consider readability - Sometimes * 2 clearer than << 1
  5. Know when to use - Optimization or specific requirements
  6. Understand limitations - JavaScript number precision
  7. Use constants for flags - Named permissions

Bit manipulation is powerful for optimization and specific problems. Master these techniques for efficient solutions.

Previous Two Pointers Technique - Complete Guide Interval Problems - Complete Guide Next