Skip to main content
Mapagam

Using Bit Manipulation

1. Working with Bitwise Operators

Operator Name Description Example
& AND Performs bitwise AND operation on each bit pair 5 & 3 = 1 (binary: 101 & 011 = 001)
| OR Performs bitwise OR operation on each bit pair 5 | 3 = 7 (binary: 101 | 011 = 111)
^ XOR Performs bitwise XOR operation on each bit pair 5 ^ 3 = 6 (binary: 101 ^ 011 = 110)
~ NOT Flips all bits (complement) ~5 = -6 (binary: ~101 = ...11111010)
<< Left Shift Shifts bits to the left, filling with zeros 5 << 1 = 10 (binary: 101 << 1 = 1010)
>> Right Shift Shifts bits to the right, preserving sign (arithmetic) 5 >> 1 = 2 (binary: 101 >> 1 = 010)
>>> Zero-fill Right Shift Shifts bits to the right, filling with zeros (logical) 5 >>> 1 = 2 (binary: 101 >>> 1 = 010)

Example: Checking if a Number is Odd or Even

function isOdd(num) {
  return (num & 1) === 1;
}

console.log(isOdd(5)); // true
console.log(isOdd(4)); // false

Example: Swapping Two Numbers Without Temporary Variable

let a = 10;
let b = 20;

a = a ^ b; // a becomes 30 (10^20)
b = a ^ b; // b becomes 10 (30^20)
a = a ^ b; // a becomes 20 (30^10)

console.log(a); // 20
console.log(b); // 10

Example: Setting a Bit at Position

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

let num = 5; // binary: 101
num = setBit(num, 2); // Set bit at position 2 (0-indexed)
console.log(num); // 13 (binary: 1101)

Example: Clearing a Bit at Position

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

let num = 13; // binary: 1101
num = clearBit(num, 2); // Clear bit at position 2 (0-indexed)
console.log(num); // 5 (binary: 101)

2. Checking Set Bits

Operation Description Example Notes
n & (1 << i) Checks if bit at position i is set 
let n = 5; // Binary: 101
let i = 2;
console.log(n & (1 << i)); // Output: 4 (bit is set)
 Use left shift to create mask for bit at position i
n & (n - 1) Removes the rightmost set bit 
let n = 12; // Binary: 1100
console.log(n & (n - 1)); // Output: 8 (Binary: 1000)
 Useful for counting set bits efficiently
n & (-n) Extracts the rightmost set bit 
let n = 12; // Binary: 1100
console.log(n & (-n)); // Output: 4 (Binary: 100)
 Uses two's complement to isolate rightmost set bit
popcount(n) Counts total number of set bits 
let n = 13; // Binary: 1101
console.log(n.toString(2).split('1').length - 1); // Output: 3
 Can be implemented using built-in functions or bit manipulation

3. Setting and Clearing Bits

Operation Expression Description
Set bit at position n num | (1 << n) Turns on the bit at position n
Clear bit at position n num & ~(1 << n) Turns off the bit at position n
Toggle bit at position n num ^ (1 << n) Flips the bit at position n

Example: Setting and Clearing Bits

let num = 5; // Binary: 101
console.log("Original number:", num, "(binary: " + num.toString(2) + ")");

// Set bit at position 1
num = num | (1 << 1);
console.log("After setting bit 1:", num, "(binary: " + num.toString(2) + ")");

// Clear bit at position 2
num = num & ~(1 << 2);
console.log("After clearing bit 2:", num, "(binary: " + num.toString(2) + ")");

4. Toggling Bits

Bit toggling is the process of flipping a bit from 0 to 1 or from 1 to 0. This is commonly achieved using the XOR operator (^) with a mask.

Operation Expression Description
Toggle bit at position i num ^ (1 << i) Flips the bit at index i of num

Example: Toggling a Bit

let num = 0b1010; // Binary: 10, Decimal: 10
let i = 2;        // Toggle bit at position 2

num ^= (1 << i);  // Result: 0b1110 = 14

console.log(num.toString(2)); // Output: "1110"
Note: The mask 1 << i creates a number with only the i-th bit set to 1. XORing with this mask flips that specific bit.

5. Finding Single Number

Given an array where every element appears twice except for one, find the single number using XOR bit manipulation.

Property Description
XOR Operation For any number n, n ^ n = 0 and n ^ 0 = n.

Example: Find Single Number in Array

const findSingleNumber = (nums) => {
  let result = 0;
  for (let num of nums) {
    result ^= num;
  }
  return result;
};

// Example usage:
const nums = [2, 3, 2, 4, 4];
console.log(findSingleNumber(nums)); // Output: 3
Note: This approach works only if all elements appear exactly twice except one.

6. Finding Two Single Numbers

Given an array where every element appears twice except for two elements that appear only once, find the two unique numbers using bit manipulation.

Property Description
XOR Operation Used to cancel out duplicate numbers. XOR of all elements gives XOR of the two unique numbers.
Isolate Rightmost Set Bit Find the rightmost set bit in XOR result to differentiate between two unique numbers.

Example: Finding Two Single Numbers

function findTwoSingleNumbers(arr) {
  let xor = 0;
  for (let num of arr) {
    xor ^= num;
  }

  // Isolate the rightmost set bit
  let rightmostSetBit = xor & (-xor);

  let num1 = 0, num2 = 0;
  for (let num of arr) {
    if ((num & rightmostSetBit) !== 0) {
      num1 ^= num;
    } else {
      num2 ^= num;
    }
  }

  return [num1, num2];
}

// Example usage:
const nums = [1, 2, 1, 3, 2, 5];
console.log(findTwoSingleNumbers(nums)); // [3, 5]
Note: The XOR operation cancels out duplicates, leaving only the XOR of the two unique numbers. By isolating a bit that is set in one number but not the other, we can partition the array into two groups and XOR each group to find the unique numbers.

7. Counting Set Bits

Method Description Time Complexity Space Complexity
Built-in Function Use Integer.bitCount() in Java or bin(n).count('1') in Python O(1) O(1)
Brian Kernighan's Algorithm Repeatedly clear the least significant set bit using n & (n - 1) O(k), where k is the number of set bits O(1)
Lookup Table Precompute counts for all 8-bit values and use them to count bits in larger numbers O(1) for 8-bit chunks O(256) = O(1)

Example: Brian Kernighan's Algorithm

public static int countSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

Example: Built-in Function in Python

n = 15
count = bin(n).count('1')
print(count)  // Output: 4
Note: The built-in function is usually the fastest and most readable for practical use.

8. Checking Power of Two

Use bit manipulation to efficiently check if a number is a power of two.

Condition Description Implementation
n & (n - 1) == 0 For a power of two, only one bit is set. Subtracting 1 flips all bits after the set bit. Bitwise AND of n and (n-1) will be zero. 
function isPowerOfTwo(n) {
  return n & (n - 1) === 0 && n > 0;
}
n & (n - 1) == 0 and n > 0 Ensures that n is positive, as negative numbers and zero are not powers of two. 
function isPowerOfTwo(n) {
  return n & (n - 1) === 0 && n > 0;
}

Example: isPowerOfTwo

console.log(isPowerOfTwo(8));  // true
console.log(isPowerOfTwo(6));  // false

9. Reversing Bits

Operation Description Example
Reverse bits of a 32-bit integer Reverses the order of all 32 bits in an integer. 
function reverseBits(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>= 1;
  }
  return result;
}
Reverse bits in groups of 4 (nibbles) Reverses the order of nibbles (4-bit chunks) in a 32-bit integer. 
function reverseNibbles(n) {
  let result = 0;
  for (let i = 0; i < 8; i++) {
    result = (result << 4) | (n & 0xF);
    n >>= 4;
  }
  return result;
}

Example: Reversing Bits of a Number

const num = 0b11001010; // Binary: 11001010
const reversed = reverseBits(num);
console.log(reversed.toString(2)); // Output: 01010011

10. Finding Missing Number

Approach Description Time Complexity Space Complexity
XOR Use XOR properties: a ^ a = 0, a ^ 0 = a. XOR all indices and values, then XOR with n to find missing number. O(n) O(1)
Mathematical Sum Calculate expected sum of 0 to n, subtract actual sum to find missing number. O(n) O(1)

Example: XOR Approach

function findMissingXOR(nums) {
  let xor = 0;
  const n = nums.length;

  for (let i = 0; i < n; i++) {
    xor ^= i ^ nums[i];
  }

  return xor ^ n;
}

// Example usage:
// Input: [0, 1, 3]
// Output: 2

Example: Mathematical Sum

function findMissingSum(nums) {
  const n = nums.length;
  const expectedSum = (n * (n + 1)) / 2;
  const actualSum = nums.reduce((sum, num) => sum + num, 0);
  return expectedSum - actualSum;
}

// Example usage:
// Input: [0, 1, 3]
// Output: 2

11. Generating Power Set

The power set of a set is the set of all possible subsets of that set. For a set with n elements, the power set contains 2^n subsets.

Approach Description Time Complexity Space Complexity
Bitmasking Each subset can be represented by a bitmask of n bits, where each bit represents whether to include the corresponding element. O(n * 2^n) O(2^n)
Recursive Recursively build subsets by including or excluding each element. O(n * 2^n) O(2^n)
Iterative Start with an empty set and iteratively add elements to existing subsets. O(n * 2^n) O(2^n)

Example: Bitmasking Approach

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

// Example usage:
const nums = [1, 2, 3];
console.log(generatePowerSet(nums));
// Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Example: Recursive Approach

function generatePowerSetRecursive(nums) {
  const result = [];
  
  function backtrack(start, currentSubset) {
    result.push([...currentSubset]);
    
    for (let i = start; i < nums.length; i++) {
      currentSubset.push(nums[i]);
      backtrack(i + 1, currentSubset);
      currentSubset.pop();
    }
  }
  
  backtrack(0, []);
  return result;
}

// Example usage:
const nums = [1, 2, 3];
console.log(generatePowerSetRecursive(nums));
// Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Note: The bitmask approach is efficient for generating all subsets, especially when the size of the set is small. It leverages bit operations to efficiently iterate through all combinations.

12. Solving Bitwise AND Range

Property Description Example
bitwise AND Performs bitwise AND operation on two numbers 5 & 3 = 1
range AND AND operation on all numbers in a range [left, right] 5 & 6 & 7

Example: Range AND Calculation

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

// Example usage:
console.log(rangeBitwiseAnd(5, 7)); // Output: 4
Note: The key insight is that the leftmost bits remain the same, and we can find the common prefix of left and right.

Was this article helpful?

Related Cheat Sheets