A lesson from the Algorithms & Patterns module of the bootcamp. About an 11 minute read.
Numbers are bit patterns, and the bitwise operators let you work on all of those bits at once. This is the most self-contained topic here: a handful of identities, each of which turns a specific problem into one line. Learn the identities and why they hold, not a list of tricks, because the reasoning is what lets you invent the fifth one when you need it.
AND (&) keeps a bit only if both numbers have it, which makes it a MASK: x & mask keeps exactly the bits the mask allows. OR (|) turns bits on. XOR (^) turns on a bit where the two differ, which makes it a TOGGLE. NOT (~) flips everything. Left shift (<<) multiplies by 2 per step, and right shift (>>) divides by 2. The most useful way to think about it: an integer is a SET of the positions where its bits are 1. Then AND is intersection, OR is union, XOR is symmetric difference, and 1 << i is the set containing just i. Most bit problems become obvious the moment you read them as set operations instead of arithmetic.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 576 practice puzzles