🔢 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

Concept

Operation	Symbol	Example	Result
AND	&	5 & 3	1
OR	|	5 | 3	7
XOR	^	5 ^ 3	6
NOT	~	~5	-6
Left shift	<<	5 << 1	10
Right shift	>>	5 >> 1	2

Key XOR properties: a^a=0, a^0=a, commutative, associative.

---

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

---

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

---

Related Topics

• Math
• School Basics — XOR swap covered there

← Back to Home · © sparshjaswal