Bit Manipulation
An integer read as 32 or 64 independent flags, and the masks that get, set, clear, count and enumerate them.
Bit Manipulation: Read one bit
Under every integer is a fixed row of bits. This category treats that row as data rather than as a number: bit i is read with (n >> i) & 1, turned on by an OR with 1 << i, turned off by an AND with the inverse of that same mask, and flipped by an XOR with it. Each of those is one machine instruction, and the whole row is touched at once.
A handful of identities do most of the work. n & (n - 1) clears the lowest set bit, so a loop on it runs once per 1 bit instead of once per bit position, and it gives a power-of-two test in a single step. n & -n keeps only that lowest bit, which is exactly the step a Fenwick tree takes. XOR is its own inverse and equal values cancel, so XOR across a list where everything appears twice leaves only the value that does not.
The larger use is a set held in a register. For n up to about 20, a bitmask stores a subset of n items in one integer: union is OR, intersection is AND, membership is a shift and an AND, and counting from 0 to 2^n - 1 walks every subset in a fixed order. That is what makes a subset dynamic program fit into a flat array indexed by the mask. The cost is still 2^n, but with a very small constant and no allocation.
After this you can
- Get, set, clear and toggle one bit without disturbing the others
- Count set bits in one step per 1 bit rather than one per bit of width
- Hold a small set in an integer and do union, intersection and membership with operators
- Enumerate all 2^n subsets, and all submasks of a given mask, in order
- Say what XOR cancellation solves and where the trick stops working
In this order
Where people go wrong
Shifting by more than the width of the type
1 << 32 on a 32-bit integer is undefined in C and C++, and in Java the shift count is taken modulo 32, so it quietly evaluates to 1. If a mask can reach bit 32, do the arithmetic in a 64-bit type and write 1L << i.
Signed right shift on a value used as flags
An arithmetic right shift copies the sign bit down, so -8 >> 1 is -4 rather than a pattern with a zero on the left. When the integer is a row of flags rather than a number, use the unsigned shift or an unsigned type, or the top bit reappears on every step and a loop on it never ends.
Operator precedence in a bitwise test
In the C family, & and | bind more loosely than == and !=, so n & 1 == 0 parses as n & (1 == 0), which is always 0. Put parentheses around every bitwise expression you compare.