Algorithms · 4 lessons
Bit ManipulationWorking directly with ones and zeroes
An integer in memory is just a run of bits. AND, OR, XOR and the shifts are each a single CPU instruction, and used well they collapse some problems to constant time — or let one integer stand in for a whole set.
Why learn Bit Manipulation
Where it shows upPermissions and feature flags
Read, write and execute take one bit each, so one integer holds the lot. Unix's chmod 755 and a game's status flags work this way.
→ Lesson: Bitwise BasicsFinding the one that is alone
Every value appears twice except one. XOR them all together and the pairs cancel, leaving the answer — with no extra memory at all.
→ Lesson: XOR TricksNetmasks and hashing
Subnet masks, replacing a hash table's modulo with an AND, Bloom filters — all bit operations underneath.
→ Lesson: Counting BitsLessons
4 lessons#AlgorithmComplexityDifficultyStatus
01Bitwise Basics The basic operationsAND / OR / XOR / NOT and shifts; getting, setting and clearing a bitUsed for: Permission flags, hardware registers, compact storageO(1)Space O(1)available02XOR Tricks XOR tricksa ^ a = 0 and a ^ 0 = a — swapping and cancellingUsed for: Single Number, the missing number, swapping without a temporaryO(n)Space O(1)available03Counting Bits Counting bitsBrian Kernighan's n & (n−1)Used for: Hamming distance, population countO(n)Space O(1)available04Subset Enumeration Enumerating subsets with bitsEvery integer from 0 to 2ⁿ−1 is one subsetUsed for: Small combinatorial problems, the setup for bitmask DPO(2ⁿ)Space O(1)available