Bit Manipulation
The Bit Manipulation Pattern
Work on the binary form of a number directly instead of on its decimal value. A few identities carry most interview questions: n & (n - 1) clears the lowest set bit, x ^ x = 0 cancels pairs, n >> 1 and n & 1 walk the bits one at a time, and & with ^ add two numbers without the + operator.
Interactive problems
How do you recognise a bit manipulation problem?
The problem talks about bits, binary representations, powers of two, or asks for O(1) extra space on a counting or "find the missing or single one" task, where XOR cancelling pairs or a bit mask replaces a hash set.
What is the time complexity of the bit manipulation pattern?
O(number of bits) per number, which is O(1) for fixed-width integers, with O(1) extra space — against O(n) extra space for the hash set or array a counting approach would use.
Bit Manipulation practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Bit Manipulation problems by difficulty and complexity
The difficulty, running time and extra space of every bit manipulation solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Number of 1 Bits | Easy | Ω(1) | Θ(k) | O(32) | O(1) |
| Single Number | Easy | Ω(n) | Θ(n) | O(n) | O(1) |
| Missing Number | Easy | Ω(n) | Θ(n) | O(n) | O(1) |
| Reverse Bits | Easy | Ω(32) | Θ(32) | O(32) | O(1) |
| Sum of Two Integers | Medium | Ω(1) | Θ(1) | O(32) | O(1) |
| Pow(x, n) | Medium | Ω(log n) | Θ(log n) | O(log n) | O(1) |
| Reverse Integer | Medium | Ω(log |x|) | Θ(log |x|) | O(log |x|) | O(1) |
Related patterns and concepts
The underlying technique is covered from first principles in the bit manipulation lesson in the DSA visualizer curriculum. Bit Manipulation is one of the 18 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Two Pointers · 26 lessons
- Introduction to Two PointersFree
- Reverse String
- Two Sum II - Input Array Is SortedFree
- Valid Palindrome
- Merge Sorted Array
- Remove Duplicates from Sorted Array
- Remove Element
- Rotate Array
- Squares of a Sorted Array
- Is Subsequence
- Valid Palindrome II
- Longest Palindromic Substring
- Palindromic Substrings
- Encode and Decode Strings
- Container With Most Water
- 3-Sum
- 3Sum Closest
- 4Sum
- Valid Triangle Number
- Move Zeroes
- Sort Colors
- Trapping Rain Water
- Multiply Strings
- Add Binary
- Add Strings
- Plus One
Sliding Window · 14 lessons
- Introduction to Sliding WindowFree
- Longest Substring Without Repeating CharactersFree
- Longest Repeating Character Replacement
- Minimum Window Substring
- Minimum Size Subarray Sum
- Max Consecutive Ones III
- Fruit Into Baskets
- Contains Duplicate II
- Overview (Fixed Length)
- Maximum Points You Can Obtain from Cards
- Maximum Sum of Distinct Subarrays With Length K
- Permutation in String
- Find All Anagrams in a String
- Sliding Window Maximum
Linked List · 16 lessons
- Linked List OverviewFree
- Reverse Linked ListFree
- Middle of the Linked ListFree
- Intersection of Two Linked ListsFree
- Merge Two Sorted ListsFree
- Add Two NumbersFree
- Linked List CycleFree
- Palindrome Linked ListFree
- Remove Nth Node From End of ListFree
- Reorder ListFree
- Swap Nodes in PairsFree
- LRU CacheFree
- Find the Duplicate NumberFree
- Copy List with Random PointerFree
- Reverse Nodes in k-GroupFree
- Happy NumberFree
Stack · 19 lessons
- Stack OverviewFree
- Valid ParenthesesFree
- Decode String
- Longest Valid Parentheses
- Overview (Monotonic Stack)
- Daily Temperatures
- Largest Rectangle in Histogram
- Maximal Rectangle
- Evaluate Reverse Polish Notation
- Min Stack
- Car Fleet
- Next Greater Element I
- Next Greater Element II
- Asteroid Collision
- Online Stock Span
- Remove K Digits
- Simplify Path
- Basic Calculator II
- Remove All Adjacent Duplicates in String
Depth-First Search · 31 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Same Tree
- Balanced Binary Tree
- Subtree of Another Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Serialize and Deserialize Binary Tree
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Count Good Nodes in Binary Tree
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree
- Longest Increasing Path in a Matrix
Breadth-First Search · 15 lessons
- Introduction to BFSFree
- BFS OverviewFree
- Binary Tree Level Order Sum
- Binary Tree Level Order Traversal
- Symmetric Tree
- Binary Tree Rightmost Node
- Binary Tree Zigzag Level Order Traversal
- Maximum Width of Binary Tree
- Graphs OverviewFree
- Minimum Knight Moves
- Rotting Oranges
- 01 Matrix
- Bus Routes
- Word Ladder
- Cheapest Flights Within K Stops
Dynamic Programming · 32 lessons
- Intro to Dynamic ProgrammingFree
- Solving a Question with DPFree
- Fibonacci Number
- Counting Bits
- Pascal's Triangle
- Min Cost Climbing Stairs
- House Robber
- House Robber II
- House Robber III
- Coin Change
- Coin Change II
- Maximum Product Subarray
- Combination Sum IV
- Partition Equal Subset Sum
- Target Sum
- Decode Ways
- Maximal Square
- Unique Paths
- Unique Paths II
- Minimum Path Sum
- Triangle
- Longest Common Subsequence
- Edit Distance
- Interleaving String
- Distinct Subsequences
- Regular Expression Matching
- Wildcard Matching
- Burst Balloons
- Best Time to Buy and Sell Stock with Cooldown
- Longest Increasing Subsequence
- Word Break
- Maximum Profit in Job Scheduling