Skip to main content

Bit Manipulation Basics

Bit Manipulation Basics​

Bit manipulation involves using bitwise operators to perform operations on binary representations of numbers. This technique is useful in various programming scenarios, including optimization, cryptography, and low-level data processing.

Basic Bitwise Operators​

  1. AND (&):

    • Description: Performs a bitwise AND operation.
    • Example: 
      const a = 5;  // 0101 in binary
      const b = 3;  // 0011 in binary
      const result = a & b;  // 0001 in binary (1 in decimal)

  2. OR (|):

    • Description: Performs a bitwise OR operation.
    • Example: 
      const a = 5;  // 0101 in binary
      const b = 3;  // 0011 in binary
      const result = a | b;  // 0111 in binary (7 in decimal)

  3. XOR (^):

    • Description: Performs a bitwise XOR operation.
    • Example: 
      const a = 5;  // 0101 in binary
      const b = 3;  // 0011 in binary
      const result = a ^ b;  // 0110 in binary (6 in decimal)

  4. NOT (~):

    • Description: Performs a bitwise NOT operation (inverts all bits).
    • Example: 
      const a = 5;  // 0101 in binary
      const result = ~a;  // 1010 in binary (in 32-bit system: -6 in decimal)

  5. Left Shift (<<):

    • Description: Shifts bits to the left, filling with zeros.
    • Example: 
      const a = 5;  // 0101 in binary
      const result = a << 1;  // 1010 in binary (10 in decimal)

  6. Right Shift (>>):

    • Description: Shifts bits to the right, preserving the sign bit.
    • Example: 
      const a = 5;  // 0101 in binary
      const result = a >> 1;  // 0010 in binary (2 in decimal)

  7. Unsigned Right Shift (>>>):

    • Description: Shifts bits to the right, filling with zeros (ignores the sign bit).
    • Example: 
      const a = -5; // 1111111111111111111111111111011 in binary (32-bit)
      const result = a >>> 1; // 0111111111111111111111111111101 in binary (2147483645 in decimal)

Common Bit Manipulation Techniques​

  1. Check if a Number is Even or Odd:

    • Description: Use bitwise AND with 1.
    • Example: 
      const isOdd = (num) => (num & 1) === 1;
      const isEven = (num) => (num & 1) === 0;

  2. Toggle a Bit:

    • Description: Use XOR with 1 to flip the bit.
    • Example: 
      const toggleBit = (num, bitPosition) => num ^ (1 << bitPosition);

  3. Set a Bit:

    • Description: Use OR with 1 shifted to the bit position.
    • Example: 
      const setBit = (num, bitPosition) => num | (1 << bitPosition);

  4. Clear a Bit:

    • Description: Use AND with the negation of 1 shifted to the bit position.
    • Example: 
      const clearBit = (num, bitPosition) => num & ~(1 << bitPosition);

  5. Count Number of Set Bits (Hamming Weight):

    • Description: Count the number of 1s in the binary representation.
    • Example: 
      const countSetBits = (num) => {
        let count = 0;
        while (num > 0) {
          count += num & 1;
          num >>= 1;
        }
        return count;
      };

  6. Brian Kernighan’s Algorithm:

    • Description: Efficiently counts the number of set bits in an integer. It repeatedly clears the least significant set bit and counts the number of operations.
    • Example: 
      const countSetBits = (num) => {
        let count = 0;
        while (num) {
          num &= (num - 1);  // Clear the least significant bit set
          count++;
        }
        return count;
      };

  7. Find the Rightmost Set Bit:

    • Description: Use num & -num.
    • Example: 
      const rightmostSetBit = (num) => num & -num;

  8. Find the Position of the Rightmost Set Bit:

    • Description: Use Math.log2(num & -num).
    • Example: 
      const rightmostSetBitPosition = (num) => Math.log2(num & -num);

  9. Swap Two Numbers Without a Temporary Variable:

    • Description: Use XOR to swap values.
    • Example: 
      const swap = (a, b) => {
        a ^= b;
        b ^= a;
        a ^= b;
      };

  10. Clear All Bits from MSB to a Specific Bit

    • Clear all bits from the most significant bit (MSB) to a specific position.

      let number = 13; // Binary: 1101
      let position = 2;

      let newNumber = number & ((1 << position) - 1);  //Formula
      console.log(newNumber); // Output: 1 (Binary: 0001)

  11. Clear All Bits from a Specific Bit to LSB

    • Clear all bits from a specific position to the least significant bit (LSB).

      let number = 13; // Binary: 1101
      let position = 1;

      let newNumber = number & ~((1 << (position + 1)) - 1);
      console.log(newNumber); // Output: 8 (Binary: 1000)

  12. Extract a Range of Bits

    • Extract a specific range of bits (e.g., from start to end).

      let number = 29; // Binary: 11101
      let start = 1;
      let end = 3;

      let extracted = (number >> start) & ((1 << (end - start + 1)) - 1);
      console.log(extracted); // Output: 6 (Binary: 110)

  13. Set a Range of Bits

    • Set a range of bits to 1.

      let number = 8; // Binary: 1000
      let start = 1;
      let end = 3;

      let newNumber = number | (((1 << (end - start + 1)) - 1) << start);
      console.log(newNumber); // Output: 14 (Binary: 1110)

Use Cases​

  • Data Compression: Efficiently store and manipulate data using bitwise operations.
  • Cryptography: Implement cryptographic algorithms and protocols.
  • Network Protocols: Handle and process network data at the bit level.
  • Performance Optimization: Use bit manipulation for performance-critical code.

XOR (^) Operations Cheatsheet for Coding Interviews

Basic Properties of XOR​

1. Fundamental Rules​

// 1. XOR with 0
x ^ 0 = x            // XOR with 0 returns the number itself

// 2. XOR with itself
x ^ x = 0            // XOR of a number with itself is 0

// 3. XOR is commutative
a ^ b = b ^ a        // Order doesn't matter

// 4. XOR is associative
(a ^ b) ^ c = a ^ (b ^ c)  // Grouping doesn't matter

// 5. XOR with 1
x ^ 1 = ~x           // XOR with 1 flips the bits (ones complement)

2. Important Properties​

// Self-inverse property
(a ^ b) ^ b = a      // XORing twice with same number restores original value

// Swapping values using XOR
a = a ^ b
b = a ^ b            // Now b has original value of a
a = a ^ b            // Now a has original value of b

// XOR of all bits
function xorOfAllBits(n) {
    switch(n % 4) {
        case 0: return n;     // If n % 4 = 0, xor = n
        case 1: return 1;     // If n % 4 = 1, xor = 1
        case 2: return n + 1; // If n % 4 = 2, xor = n + 1
        case 3: return 0;     // If n % 4 = 3, xor = 0
    }
}

Common XOR Patterns in Coding Problems​

1. Find Single Number​

Finding a number that appears once while others appear twice.

function findSingle(arr) {
    let result = 0;
    for (let num of arr) {
        result ^= num;
    }
    return result;
}

// Example
console.log(findSingle([4,1,2,1,2])); // Output: 4

2. Find Two Single Numbers​

Finding two numbers that appear once while others appear twice.

function findTwoSingle(arr) {
    // 1. XOR all numbers
    let xorResult = 0;
    for (let num of arr) {
        xorResult ^= num;
    }
    
    // 2. Find rightmost set bit in xorResult
    let rightmostSetBit = 1;
    while ((xorResult & rightmostSetBit) === 0) {
        rightmostSetBit <<= 1;
    }
    
    // 3. Divide elements into two groups
    let x = 0, y = 0;
    for (let num of arr) {
        if (num & rightmostSetBit) {
            x ^= num;
        } else {
            y ^= num;
        }
    }
    
    return [x, y];
}

// Example
console.log(findTwoSingle([1,2,1,3,2,5])); // Output: [3,5]

3. Missing Number​

Finding missing number in array containing n distinct numbers in range [0, n].

function findMissing(arr) {
    let n = arr.length;
    let result = n;  // XOR with n first
    
    for (let i = 0; i < n; i++) {
        result ^= i ^ arr[i];  // XOR with both index and value
    }
    
    return result;
}

// Example
console.log(findMissing([3,0,1])); // Output: 2

4. Finding Duplicate Number​

Finding duplicate in array where one number appears twice.

function findDuplicate(arr) {
    let result = 0;
    // XOR all numbers from 1 to n-1
    for (let i = 1; i < arr.length; i++) {
        result ^= i;
    }
    // XOR with all array elements
    for (let num of arr) {
        result ^= num;
    }
    return result;
}

Advanced XOR Applications​

1. Bit Manipulation with XOR​

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

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

// Count set bits using XOR
function countSetBits(num) {
    let count = 0;
    while (num) {
        num = num & (num - 1);  // Clear rightmost set bit
        count++;
    }
    return count;
}

2. XOR for Encryption/Decryption​

function xorEncrypt(text, key) {
    let encrypted = '';
    for (let i = 0; i < text.length; i++) {
        encrypted += String.fromCharCode(text.charCodeAt(i) ^ key);
    }
    return encrypted;
}

// Decryption is the same operation
const decrypt = xorEncrypt;  // XOR is self-inverse

3. XOR in Matrix Operations​

// XOR of all elements in matrix
function matrixXOR(matrix) {
    let result = 0;
    for (let row of matrix) {
        for (let val of row) {
            result ^= val;
        }
    }
    return result;
}

// Check if row/column XOR is valid
function isValidXORMatrix(matrix) {
    const n = matrix.length;
    for (let i = 0; i < n; i++) {
        let rowXOR = 0, colXOR = 0;
        for (let j = 0; j < n; j++) {
            rowXOR ^= matrix[i][j];
            colXOR ^= matrix[j][i];
        }
        if (rowXOR !== colXOR) return false;
    }
    return true;
}

Common Interview Problem Patterns​

1. Adjacent XOR Problems​

// Check if array can be derived from adjacent XOR
function canDeriveFromAdjacent(derived) {
    let original = 0;
    for (let i = 0; i < derived.length - 1; i++) {
        original ^= derived[i];
    }
    return derived[derived.length - 1] === (original ^ 0);
}

2. XOR Sum Problems​

// Calculate XOR sum of all pairs
function xorSumPairs(arr) {
    let result = 0;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            result ^= (arr[i] + arr[j]);
        }
    }
    return result;
}

3. XOR and Binary Trees​

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// XOR of all values in binary tree
function treeXOR(root) {
    if (!root) return 0;
    return root.val ^ treeXOR(root.left) ^ treeXOR(root.right);
}

Performance Tips​

  1. XOR operations are O(1)
  2. XOR can often replace addition/subtraction for better performance
  3. Using XOR for swapping saves memory (no temp variable needed)
  4. XOR can be used to avoid using extra space in many algorithms

Common Pitfalls​

  1. Remember that XOR is bitwise operation
  2. Don't forget about operator precedence
  3. Be careful with negative numbers
  4. Test edge cases (0, maximum values)
  5. Consider overflow in languages with fixed-size integers