Bit Manipulation
Treat integers as rows of on/off flags, learn the handful of bit tricks that matter, and use masks to enumerate subsets.
The problem
An integer is stored as a row of bits, each 0 or 1. Reading them as flags gives you three things:
- A compact way to store a set of up to 20 to 60 items in one number, called a mask.
- Tricks that run in a single machine instruction (lowest set bit, count of ones).
- A way to enumerate all subsets with a plain
forloop.
Bit positions count from 0 at the right. In 1100 (decimal 12), bits 2 and 3 are on.
1 of 9