Core · Module 12 · Lesson 4 of 4
Bit Manipulation Tricks and Submask Enumeration
Clear lowest set bits with Brian Kernighan's n & (n - 1), isolate lowest set bits with n & -n, cancel pairs with XOR, and iterate over all submasks in O(3^k) total time.
By the end you can
- Prove and apply n & (n - 1) (clear lowest set bit) and n & -n (isolate lowest set bit)
- Use XOR commutativity, associativity, and self-inverse (x ^ x = 0) to isolate unique elements in O(1) space
- Enumerate all submasks of a bitmask and prove why nested submask enumeration over k bits takes O(3^k) instead of O(4^k)
Builds on Bits, bytes and number representation, Combinatorics, Modular nCr, and the Pigeonhole Principle.
01 · A question first
Iterating over every mask of k bits and then testing all 2^k possible submasks takes O(4^k) operations; a one-line bitwise trick `sub = (sub - 1) & mask` visits ONLY valid submasks in O(3^k) total time. How does subtracting 1 and masking jump straight to the next valid subset?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Intuitive Explanation & Real-World Analogy
- Core Concepts & Visual Walkthrough
- Pseudocode
- Multi-Language Implementations (C++, Java, Python)
- Time & Auxiliary Space Complexity Derivation
- Edge Cases & Common Beginner Mistakes
- Alternative Approaches (Brute Force vs. Optimal)
- Pattern Recognition Guide & Three-Stage Practice Plan
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem