Bit Manipulation
An integer read as 32 or 64 independent flags, and the masks that get, set, clear, count and enumerate them.
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
The mask 1 shl 4 is 16, a single 1 at bit 4. Bit 4 of 178 is currently 1. Shift 178 right by 4 and keep the last bit.
In this order
- Get BitShift right by i and keep the last bit.
- Set BitOR with a mask that has a single 1 at bit i.
- Clear BitAND with the inverse of that mask, so only bit i is forced to 0.
- Toggle BitXOR with the mask flips bit i and nothing else.
- Count Set BitsClear the lowest 1 with n and (n - 1) until nothing is left, counting rounds.
- Brian Kernighan's Algorithmn and (n - 1) wipes the lowest set bit, so the loop runs once per 1 bit.
- Power of Two CheckExactly one 1 bit, so clearing the lowest one leaves zero.
- Lowest Set Bitn and -n keeps only the lowest 1. It is the step a Fenwick tree takes.
- XOR Propertiesa ^ a = 0, a ^ 0 = a, commutative and associative; pairs cancel.
- XOR Pairing (Single Number)XOR everything; duplicates cancel and the unpaired value remains.
- Gray Codeg = n xor (n shr 1); each row of codes flips exactly one bit of the row above.
- BitmaskUse the bits of an integer as a set of booleans.
- Subset EnumerationCounting from 0 to 2^n - 1 enumerates every subset; sub = (sub - 1) & mask enumerates submasks.
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.
Or a different category
Hashing
The set is large, or the elements are not small integers you can number, so a hash set costs less than a mask does.
Dynamic Programming
The mask is only the index into a table and the difficulty is the recurrence over subsets, not the bit operations.