The Complete Guide to Bit Manipulation in JavaScript

Introduction

Bit manipulation is one of the most powerful techniques in competitive programming and system design. It involves working directly with the binary representation of numbers (0s and 1s) to solve problems efficiently.

Why Learn Bit Manipulation?

⚡ Speed: Bitwise operations are among the fastest operations a CPU can perform
💾 Memory Efficient: Use single bits to store boolean flags
🧠 Elegant Solutions: Many complex problems have simple bit manipulation solutions

JavaScript Number System

// JavaScript numbers are 64-bit floats (IEEE 754)
// But bitwise operators convert them to 32-bit signed integers
console.log(Number.MAX_SAFE_INTEGER); // 9007199254740991
console.log((5).toString(2)); // "101" (binary representation)

Why & When to Use Bit Manipulation?

✅ Performance: Faster than arithmetic operations.
✅ Memory Efficiency: Helps encode multiple values in one integer.
✅ Problem Solving: Used in competitive programming & interview problems.
✅ Set Operations: Working with subsets, combinations ✅ Mathematical Properties: Problems involving powers of 2, XOR properties ✅ Low-level Programming: System programming, embedded systems

👉 You use bit manipulation when:

Checking if a number is even/odd.
Swapping numbers without extra space.
Finding unique elements in an array.
Optimizing subset generation, power of 2 checks, etc.

❌ Avoid Bit Manipulation When:

Readability Matters: Team prefers clear, maintainable code
Complex Logic: Bit operations make the solution harder to understand
Debugging Difficulty: Hard to trace through bit manipulations
No Performance Gain: Simpler approaches work just as well

Bitwise Operators (with examples)

Operator	Meaning	Example
`&` (AND)	1 if both bits are 1	`5 & 3 = 1`
`	` (OR)	1 if any bit is 1
`^` (XOR)	1 if bits are different	`5 ^ 3 = 6`
`~` (NOT)	Flips all bits	`~5 = -6`
`<<` Left Shift	Shifts left (×2)	`5 << 1 = 10`
`>>` Right Shift	Shifts right (÷2, keeps sign)	`-10 >> 1 = -5`
`>>>` Unsigned Right Shift	Shifts right, fills 0s	`-10 >>> 1 = big positive`

Understanding Binary Basics

Binary Number System

Decimal: 5
Binary:  101
Positions: 4 2 1 (powers of 2)
           1×4 + 0×2 + 1×1 = 5

Signed vs Unsigned Integers

Signed: Can represent negative numbers using two's complement
Unsigned: Only positive numbers, uses all bits for magnitude

// Two's complement example
// -5 in binary (32-bit): 11111111111111111111111111111011
console.log((-5).toString(2)); // Shows "-101" but internally stored differently

Bit Manipulation Formulas (Cheat Sheet)

// 1. Swap two numbers
a = a ^ b; b = a ^ b; a = a ^ b;
 
// 2. Set the i-th bit
n = n | (1 << i);
 
// 3. Toggle the i-th bit
n = n ^ (1 << i);
 
// 4. Check if i-th bit is set
isSet = (n & (1 << i)) !== 0;
 
// 5. Clear the i-th bit
n = n & ~(1 << i);
 
// 6. Check if number is odd
isOdd = (n & 1) === 1;
 
// 7. Count set bits (Brian Kernighan’s Algo)
count = 0;
while (n > 0) { n = n & (n - 1); count++; }
 
// 8. Rightmost set bit
rmsb = n & -n;
 
// 9. Gray Code
gray = n ^ (n >> 1);
 
// 10. Check Power of 2
isPow2 = n > 0 && (n & (n - 1)) === 0;
 
// 11. Turn off rightmost set bit
n = n & (n - 1);
 
// 12. Isolate rightmost 0 bit
res = ~n & (n + 1);

Common Problem Approaches

Find the single number (others appear twice)

function singleNumber(nums) {
  let ans = 0;
  for (let n of nums) ans ^= n;
  return ans;
}
// Example: [2,2,3,4,4] → 3

Find two single numbers (others appear twice)

function singleNumber(nums) {
  let xorAll = nums.reduce((a,b)=>a^b,0);
  let rmsb = xorAll & -xorAll;
  let x = 0, y = 0;
  for (let n of nums) {
    if (n & rmsb) x ^= n;
    else y ^= n;
  }
  return [x,y];
}
// Example: [1,2,1,3,2,5] → [3,5]

Count number of 1 bits (Hamming Weight)

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= (n - 1);
    count++;
  }
  return count;
}
// Example: n=11 (1011) → 3

Check if a number is Power of 2

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}
// Example: 8 → true, 10 → false

Find missing number in 0..n

function missingNumber(nums) {
  let n = nums.length;
  let ans = 0;
  for (let i = 0; i <= n; i++) ans ^= i;
  for (let num of nums) ans ^= num;
  return ans;
}
// Example: [3,0,1] → 2

Bitwise Operators Deep Dive

1. AND `(&)` - Both bits must be 1

// Truth Table:
// 0 & 0 = 0    1 & 0 = 0
// 0 & 1 = 0    1 & 1 = 1
 
console.log(5 & 3); // 1
// 5: 101
// 3: 011
// &: 001 = 1
 
// Use Case: Check if number is even
function isEven(n) {
    return (n & 1) === 0; // Last bit is 0 for even numbers
}

2. OR `(|)` - At least one bit must be 1

// Truth Table:
// 0 | 0 = 0    1 | 0 = 1
// 0 | 1 = 1    1 | 1 = 1
 
console.log(5 | 3); // 7
// 5: 101
// 3: 011
// |: 111 = 7
 
// Use Case: Set a specific bit
function setBit(n, i) {
    return n | (1 << i);
}

3. XOR `(^)` - Bits must be different

// Truth Table:
// 0 ^ 0 = 0    1 ^ 0 = 1
// 0 ^ 1 = 1    1 ^ 1 = 0
 
console.log(5 ^ 3); // 6
// 5: 101
// 3: 011
// ^: 110 = 6
 
// Use Case: Swap without temp variable
function swap(a, b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    return [a, b];
}

4. NOT `(~)` - Flip all bits

console.log(~5); // -6
// Why -6? Two's complement: ~n = -(n + 1)
 
// Use Case: Clear a specific bit
function clearBit(n, i) {
    return n & ~(1 << i);
}

5. Left Shift `(<<)` - Multiply by `2^n`

console.log(5 << 2); // 20
// 5: 101
// <<2: 10100 = 20
// Formula: n << i = n × 2^i

6. Right Shift (>>) - Divide by 2^n (signed)

console.log(20 >> 2); // 5
console.log(-20 >> 2); // -5 (sign preserved)
// Formula: n >> i = floor(n / 2^i)

7. Unsigned Right Shift (>>>) - Divide by 2^n (unsigned)

console.log(-20 >>> 2); // 1073741819
// Fills left bits with 0, treats as unsigned

Essential Bit Manipulation Patterns

Pattern 1: Check, Set, Clear, Toggle Bits

class BitOperations {
    // Check if i-th bit is set
    static checkBit(n, i) {
        return (n & (1 << i)) !== 0;
    }
    
    // Set the i-th bit
    static setBit(n, i) {
        return n | (1 << i);
    }
    
    // Clear the i-th bit
    static clearBit(n, i) {
        return n & ~(1 << i);
    }
    
    // Toggle the i-th bit
    static toggleBit(n, i) {
        return n ^ (1 << i);
    }
}
 
// Example usage
let n = 5; // 101 in binary
console.log(BitOperations.checkBit(n, 2)); // true (bit 2 is set)
console.log(BitOperations.setBit(n, 1));   // 7 (111 in binary)
console.log(BitOperations.clearBit(n, 2)); // 1 (001 in binary)
console.log(BitOperations.toggleBit(n, 1)); // 7 (111 in binary)

Pattern 2: Count Set Bits (Brian Kernighan's Algorithm)

function countSetBits(n) {
    let count = 0;
    while (n > 0) {
        n = n & (n - 1); // Removes rightmost set bit
        count++;
    }
    return count;
}
 
// Alternative: Built-in method
function countSetBitsBuiltIn(n) {
    return n.toString(2).split('1').length - 1;
}
 
console.log(countSetBits(7)); // 3 (111 has 3 set bits)

Pattern 3: Power of 2 Check

function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
}
 
console.log(isPowerOfTwo(8)); // true
console.log(isPowerOfTwo(6)); // false
 
// Why it works:
// Power of 2: 8 = 1000, 8-1 = 0111, 8 & 7 = 0000
// Not power of 2: 6 = 0110, 6-1 = 0101, 6 & 5 = 0100 ≠ 0

Pattern 4: Get Rightmost Set Bit

function getRightmostSetBit(n) {
    return n & -n;
}
 
console.log(getRightmostSetBit(12)); // 4
// 12 = 1100, rightmost set bit is at position 2 (value 4)

Problem-Solving Approaches

Approach 1: XOR for Finding Unique Elements

Problem: Find the element that appears once while all others appear twice.

function findSingle(nums) {
    let result = 0;
    for (let num of nums) {
        result ^= num; // XOR cancels out duplicate pairs
    }
    return result;
}
 
console.log(findSingle([4, 1, 2, 1, 2])); // 4
// 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 (since 1^1=0 and 2^2=0)

Approach 2: Bit Masking for Subsets

Problem: Generate all subsets of a set.

function generateSubsets(nums) {
    const n = nums.length;
    const subsets = [];
    
    // 2^n possible subsets
    for (let i = 0; i < (1 << n); i++) {
        const subset = [];
        for (let j = 0; j < n; j++) {
            // Check if j-th bit is set in i
            if (i & (1 << j)) {
                subset.push(nums[j]);
            }
        }
        subsets.push(subset);
    }
    return subsets;
}
 
console.log(generateSubsets([1, 2, 3]));
// [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Approach 3: Gray Code Generation

Problem: Generate n-bit Gray code sequence.

function generateGrayCode(n) {
    const result = [];
    for (let i = 0; i < (1 << n); i++) {
        result.push(i ^ (i >> 1)); // Gray code formula
    }
    return result;
}
 
console.log(generateGrayCode(3)); // [0, 1, 3, 2, 6, 7, 5, 4]

Practice Problems with Solutions

Problem 1: Missing Number

Given: Array containing n distinct numbers from 0 to n with one missing. Find: The missing number.

function findMissingNumber(nums) {
    const n = nums.length;
    let missing = n; // Start with n
    
    for (let i = 0; i < n; i++) {
        missing ^= i ^ nums[i];
    }
    
    return missing;
}
 
// Alternative approach
function findMissingNumberV2(nums) {
    const n = nums.length;
    const expectedXor = Array.from({length: n + 1}, (_, i) => i)
                             .reduce((a, b) => a ^ b, 0);
    const actualXor = nums.reduce((a, b) => a ^ b, 0);
    return expectedXor ^ actualXor;
}
 
console.log(findMissingNumber([3, 0, 1])); // 2

Problem 2: Single Number II

Given: Array where every element appears 3 times except one. Find: The element that appears once.

function singleNumberII(nums) {
    let ones = 0, twos = 0;
    
    for (let num of nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    
    return ones;
}
 
console.log(singleNumberII([2, 2, 3, 2])); // 3

Problem 3: Reverse Bits

Given: 32-bit unsigned integer. Return: Integer with bits reversed.

function reverseBits(n) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;
    }
    return result >>> 0; // Convert to unsigned 32-bit
}
 
console.log(reverseBits(43261596)); // 964176192

Problem 4: Number of 1 Bits

Given: Positive integer. Return: Number of 1 bits in its binary representation.

function hammingWeight(n) {
    let count = 0;
    while (n !== 0) {
        count++;
        n &= (n - 1); // Remove rightmost 1 bit
    }
    return count;
}
 
console.log(hammingWeight(11)); // 3 (1011 has three 1 bits)

Problem 5: Maximum XOR of Two Numbers

Given: Array of integers. Return: Maximum XOR of any two numbers.

function findMaximumXOR(nums) {
    let maxXor = 0;
    let mask = 0;
    
    for (let i = 30; i >= 0; i--) { // 31 bits for positive numbers
        mask |= (1 << i);
        const prefixes = new Set();
        
        for (let num of nums) {
            prefixes.add(num & mask);
        }
        
        const candidate = maxXor | (1 << i);
        
        for (let prefix of prefixes) {
            if (prefixes.has(candidate ^ prefix)) {
                maxXor = candidate;
                break;
            }
        }
    }
    
    return maxXor;
}
 
console.log(findMaximumXOR([3, 10, 5, 25, 2, 8])); // 28

Performance Considerations

Time Complexity Benefits

// O(1) operations
const checkEven = n => (n & 1) === 0;           // vs n % 2 === 0
const multiplyBy8 = n => n << 3;                // vs n * 8
const divideBy4 = n => n >> 2;                  // vs Math.floor(n / 4)
const isPowerOf2 = n => n > 0 && (n & (n-1)) === 0;
 
// Benchmark example
console.time('Modulo Check');
for (let i = 0; i < 1000000; i++) {
    i % 2 === 0;
}
console.timeEnd('Modulo Check');
 
console.time('Bit Check');
for (let i = 0; i < 1000000; i++) {
    (i & 1) === 0;
}
console.timeEnd('Bit Check');

Space Complexity Benefits

// Store 8 boolean flags in 1 byte
class BitFlags {
    constructor() {
        this.flags = 0; // Single integer instead of array of booleans
    }
    
    setFlag(index) {
        this.flags |= (1 << index);
    }
    
    getFlag(index) {
        return (this.flags & (1 << index)) !== 0;
    }
    
    clearFlag(index) {
        this.flags &= ~(1 << index);
    }
}

Advanced Techniques

Technique 1: Bit Manipulation with Dynamic Programming

// Count number of 1s for all numbers from 0 to n
function countBits(n) {
    const dp = new Array(n + 1);
    dp[0] = 0;
    
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i & (i - 1)] + 1; // Remove rightmost bit and add 1
    }
    
    return dp;
}
 
console.log(countBits(5)); // [0, 1, 1, 2, 1, 2]

Technique 2: Bit Manipulation with Sliding Window

// Find maximum AND value of any subarray of size k
function maxAndSubarray(arr, k) {
    let maxAnd = 0;
    
    for (let i = 0; i <= arr.length - k; i++) {
        let currentAnd = arr[i];
        for (let j = i + 1; j < i + k; j++) {
            currentAnd &= arr[j];
        }
        maxAnd = Math.max(maxAnd, currentAnd);
    }
    
    return maxAnd;
}

Technique 3: Trie for XOR Operations

class TrieNode {
    constructor() {
        this.children = {};
        this.isEnd = false;
    }
}
 
class XORTrie {
    constructor() {
        this.root = new TrieNode();
    }
    
    insert(num) {
        let node = this.root;
        for (let i = 30; i >= 0; i--) {
            const bit = (num >> i) & 1;
            if (!(bit in node.children)) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
        }
        node.isEnd = true;
    }
    
    findMaxXOR(num) {
        let node = this.root;
        let maxXor = 0;
        
        for (let i = 30; i >= 0; i--) {
            const bit = (num >> i) & 1;
            const toggledBit = 1 - bit;
            
            if (toggledBit in node.children) {
                maxXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        
        return maxXor;
    }
}

Bubble Sort DSA Problems Patterns