Bit Manipulation Patterns — DSA Pattern
The Bit Manipulation Patterns pattern applies when you need xOR tricks, counting bits, power-of-two checks, and Hamming weight. Its time complexity is O(n) and space complexity O(1). It is used in 8 problems on Thita, including Counting Bits, Find the Difference and Missing Number. Common variations are Bitwise Operations - Power of Two/Four Check and Bitwise XOR - Finding Single/Missing Number.
Master bit manipulation including XOR tricks, counting bits, power of two checks, and bit masking. Essential for optimization and low-level problems.
Bit Manipulation Patterns is pattern 14 of 16 in the Thita.ai DSA course. It covers xOR tricks, counting bits, power-of-two checks, and Hamming weight, split into 4 subpatterns and about 1.5 hours of study. It is a depth pattern: reach for it once the interview-critical patterns are solid.
Subpatterns of Bit Manipulation Patterns
Each subpattern below has its own theory page and problem set. They are listed in the order the course teaches them.
- Bitwise Operations - Power of Two/Four Check — Check if number is power of two or four using bitwise operations. (depth topic)
- Bitwise XOR - Finding Single/Missing Number — Use XOR properties to find single number, missing number, and duplicates. (depth topic)
- Bitwise DP - Counting Bits Optimization — Count bits for range of numbers using DP with bit manipulation optimization. (depth topic)
- Bitwise AND - Counting Set Bits (Hamming Weight) — Count number of 1 bits (Hamming weight) using bitwise AND operations. (depth topic)
How to practise Bit Manipulation Patterns on Thita.ai
Read the theory for a subpattern, then solve its problems in the browser editor. Your solution runs against the problem's test cases, and the AI coach gives a hint on the technique you are missing rather than the finished answer. Progress is tracked per subpattern, so the tracker shows which of the 4 Bit Manipulation Patterns subpatterns you have covered. Topics covered here include bit manipulation, bitwise operations, XOR tricks, counting bits, power of two, bit masking, binary operations, leetcode bit manipulation.
Related DSA patterns
- Dynamic Programming (DP) Patterns — Fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break.
- Graph Traversal Patterns (DFS & BFS) — DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST.
- Design Patterns — Tries, LRU/LFU cache, and data structure design.
- Segment Tree & Fenwick Tree Patterns — Range queries, point updates, and inversion counting.
- All 16 DSA patterns
- The DSA patterns sheet
- Coding practice