🔢 Bit Manipulation

One-line summary: Operate directly on bits — XOR, AND, OR, shifts — for elegant O(1) tricks that would otherwise require O(n) logic.

Diagram

Bit Manipulation Overview Bit Manipulation GIF

🎯 Concept

Computers store integers as sequences of bits (binary digits). Bit manipulation works on these bits directly using bitwise operators, letting you replace whole loops with single, blazingly fast CPU instructions.

flowchart LR
    A["Decimal 5"] --> B["Binary 0101"]
    C["Decimal 3"] --> D["Binary 0011"]
    B --> E{"Bitwise Op"}
    D --> E
    E -->|"AND &"| F["0001 = 1"]
    E -->|"OR |"| G["0111 = 7"]
    E -->|"XOR ^"| H["0110 = 6"]

Core Operators

Operation	Symbol	Example	Result	Rule
AND	`&`	`5 & 3`	`1`	1 only if both bits are 1
OR	`\|`	`5 \| 3`	`7`	1 if either bit is 1
XOR	`^`	`5 ^ 3`	`6`	1 if bits differ
NOT	`~`	`~5`	`-6`	flips every bit
Left shift	`<<`	`5 << 1`	`10`	multiply by 2ᵏ
Right shift	`>>`	`5 >> 1`	`2`	divide by 2ᵏ (floor)

Key XOR properties: a^a=0, a^0=a, commutative, associative. These make XOR the go-to tool for "find the odd one out" problems.

Essential Bit Tricks (Cheat Sheet)

Goal	Expression
Check if `i`-th bit is set	`(n >> i) & 1`
Set the `i`-th bit	`n \| (1 << i)`
Clear the `i`-th bit	`n & ~(1 << i)`
Toggle the `i`-th bit	`n ^ (1 << i)`
Turn off lowest set bit	`n & (n - 1)`
Isolate lowest set bit	`n & (-n)`
Check power of two	`n > 0 && (n & (n - 1)) === 0`
Multiply / divide by 2	`n << 1` / `n >> 1`

⚡ Time & Space Complexity

Operation	Time	Space	Notes
Single bitwise op (`&`, `\|`, `^`, `<<`, `>>`)	O(1)	O(1)	One CPU instruction
Count set bits (Brian Kernighan)	O(k)	O(1)	k = number of set bits
Count set bits (naive scan)	O(log n)	O(1)	Iterate over all bits
Iterate all subsets via bitmask	O(2ⁿ)	O(1)	n = number of elements
Bitmask DP	O(2ⁿ · n)	O(2ⁿ)	Classic TSP-style problems

Key Insight: Bit operations are constant time regardless of the value, which is why they turn many O(n) checks into O(1).

Common Patterns

Find Single Number

const singleNumber = (nums) => nums.reduce((acc, n) => acc ^ n, 0);

Check Even/Odd

const isEven = (n) => (n & 1) === 0;

Count Set Bits (Brian Kernighan)

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

XOR Swap

let a = 5,
  b = 3;
a ^= b;
b ^= a;
a ^= b;

Power of Two Check

const isPowerOfTwo = (n) => n > 0 && (n & (n - 1)) === 0;

Pitfalls

JS bitwise ops work on 32-bit signed integers — large numbers get truncated
~n = -(n+1) — use >>> 0 to convert to unsigned if needed
XOR swap doesn't work if a and b point to the same variable

🧪 Worked Examples

Example 1: Missing Number (XOR)

Given n distinct numbers in range [0, n], find the one missing.

function missingNumber(nums) {
  let xor = nums.length; // start with n
  for (let i = 0; i < nums.length; i++) {
    xor ^= i ^ nums[i]; // cancel indices with values
  }
  return xor;
}
// Every present number cancels with its index; the missing one survives.
// Time: O(n), Space: O(1)

Example 2: Generate All Subsets (Bitmask)

Enumerate the power set of an array of size n using bit masks.

function subsets(nums) {
  const n = nums.length;
  const result = [];
  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;
}
// Each of the 2^n masks encodes one subset (bit i => include nums[i]).
// Time: O(2^n * n), Space: O(1) extra (excluding output)

Example 3: Sum of Two Integers Without `+`

Add two integers using only bitwise operations.

function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1; // bits that carry over
    a = a ^ b; // add without carry
    b = carry; // apply carry next round
  }
  return a;
}
// XOR adds bit-by-bit; AND<&lt;1 computes the carry. Repeat until no carry.
// Time: O(1) (fixed 32-bit width), Space: O(1)

Practice Problems

Easy Problems

Problem	Difficulty	Solution
LC 136 — Single Number	Easy
LC 191 — Number of 1 Bits	Easy
LC 231 — Power of Two	Easy
LC 268 — Missing Number	Easy
LC 338 — Counting Bits	Easy
LC 342 — Power of Four	Easy
LC 389 — Find the Difference	Easy
LC 401 — Binary Watch	Easy
LC 405 — Convert a Number to Hexadecimal	Easy
LC 461 — Hamming Distance	Easy
LC 476 — Number Complement	Easy
LC 693 — Binary Number with Alternating Bits	Easy
LC 762 — Prime Number of Set Bits	Easy
LC 832 — Flipping an Image	Easy
LC 868 — Binary Gap	Easy
LC 1009 — Complement of Base 10 Integer	Easy
LC 1290 — Convert Binary Number in a Linked List to Integer	Easy
LC 1342 — Number of Steps to Reduce a Number to Zero	Easy
LC 1356 — Sort Integers by The Number of 1 Bits	Easy
LC 1486 — XOR Operation in an Array	Easy
LC 1720 — Decode XORed Array	Easy
LC 2220 — Minimum Bit Flips to Convert Number	Easy
LC 2239 — Find Closest Number to Zero	Easy
CC — Little Elephant and Bits (LEBITS)	Easy
CC — Bit Difference (BITDIFF)	Easy
CC — Count Set Bits (CNTSETBIT)	Easy
CC — XOR Basics (XORBASIC)	Easy

Medium Problems

Problem	Difficulty	Solution
LC 137 — Single Number II	Medium
LC 190 — Reverse Bits	Medium
LC 201 — Bitwise AND of Numbers Range	Medium
LC 260 — Single Number III	Medium
LC 287 — Find the Duplicate Number	Medium
LC 318 — Maximum Product of Word Lengths	Medium
LC 371 — Sum of Two Integers	Medium
LC 393 — UTF-8 Validation	Medium
LC 421 — Maximum XOR of Two Numbers in an Array	Medium
LC 477 — Total Hamming Distance	Medium
LC 645 — Set Mismatch	Medium
LC 898 — Bitwise ORs of Subarrays	Medium
LC 1310 — XOR Queries of a Subarray	Medium
LC 1318 — Minimum Flips to Make a OR b Equal to c	Medium
LC 1442 — Count Triplets That Can Form Two Arrays of Equal XOR	Medium
LC 1521 — Find a Value of a Mysterious Function Closest to Target	Medium
LC 1680 — Concatenation of Consecutive Binary Numbers	Medium
LC 1734 — Decode XORed Permutation	Medium
LC 1829 — Maximum XOR for Each Query	Medium
LC 1835 — Find XOR Sum of All Pairs Bitwise AND	Medium
CC — XOR Engine (XORENG)	Medium
CC — AND OR Union (ANDORUN)	Medium
CC — Subset XOR (SUBSETXOR)	Medium
CC — Bit Manipulation Tricks (BITTRICK)	Medium

Hard Problems

Problem	Difficulty	Solution
LC 51 — N-Queens	Hard
LC 52 — N-Queens II	Hard
LC 115 — Distinct Subsequences	Hard
LC 1178 — Number of Valid Words for Each Puzzle	Hard
LC 1255 — Maximum Score Words Formed by Letters	Hard
LC 1542 — Find Longest Awesome Substring	Hard
LC 1659 — Maximize Grid Happiness	Hard
LC 1707 — Maximum XOR With an Element From Array	Hard
LC 1803 — Count Pairs With XOR in a Range	Hard
LC 1915 — Number of Wonderful Substrings	Hard
LC 2003 — Smallest Missing Genetic Value in Each Subtree	Hard
CC — Complex Bit Operations (COMPLEXBIT)	Hard
CC — Bit Masking DP (BITMASKDP)	Hard
CC — Trie with XOR (TRIEXOR)	Hard
CC — Advanced Bitwise (ADVBIT)	Hard

Math — modular arithmetic and number theory
School Basics — XOR swap covered there
Dynamic Programming — bitmask DP for subset/state problems
Recursion — subset generation via recursion vs bitmask

Diagram​

🎯 Concept​

Core Operators​

Essential Bit Tricks (Cheat Sheet)​

⚡ Time & Space Complexity​

Common Patterns​

Find Single Number​

Check Even/Odd​

Count Set Bits (Brian Kernighan)​

XOR Swap​

Power of Two Check​

Pitfalls​

🧪 Worked Examples​

Example 1: Missing Number (XOR)​

Example 2: Generate All Subsets (Bitmask)​

Example 3: Sum of Two Integers Without +​

Practice Problems​

Easy Problems​

Medium Problems​

Hard Problems​

Related Topics​