Bit Manipulation
O(1) or O(log n)Use bitwise operations to solve problems efficiently by treating integers as arrays of bits.
When to Use
- Finding single/missing numbers without extra space
- Checking if number is power of two
- Counting set bits or toggling specific bits
- XOR tricks for finding unpaired elements
Pattern Variants
XOR Tricks
Use XOR properties: a ^ a = 0, a ^ 0 = a to find unique elements.
Use for: Single Number, missing number from sequence
Bit Masks
Use AND, OR masks to check, set, or clear specific bit positions.
Use for: Power of two checks, counting bits, subset generation
Shift Operations
Use left/right shifts to multiply/divide by powers of 2 or extract bits.
Use for: Reverse bits, counting leading zeros, bit extraction
Interactive Visualization
1function singleNumber(nums) {2 let result = 034 for (const num of nums) {5 result = result ^ num6 }78 return result9}
Practice this Pattern
Single Number
Find the element that appears only once when all others appear twice using XOR
Number of 1 Bits
Count the number of set bits (1s) in a binary number (Hamming Weight)
Counting Bits
Return array where ans[i] is the number of 1s in binary of i
Reverse Bits
Reverse bits of a 32-bit unsigned integer
Missing Number
Find the missing number in array [0, n] using XOR
Power of Two
Check if a number is a power of two
Sum of Two Integers
Add two integers without using + or - operators
Single Number II
Find element appearing once when others appear 3 times
Single Number III
Find two elements appearing once when others appear twice
Bitwise AND of Range
Find bitwise AND of all numbers in range [left, right]
Number Complement
Flip all bits in binary representation
Power of Four
Check if a number is a power of four
Alternating Bits
Check if binary has alternating bits (101010...)
Hamming Distance
Count differing bit positions between two numbers
Maximum XOR
Find maximum XOR of any two numbers in array
Maximum XOR of Two Numbers (Trie)
Use bitwise trie to maximize xor value