Bits

Bit Manipulation

Operators, masks, tricks and subset enumeration.

Bitwise Operators
▶ viz

The six primitive operations on the binary representation of integers: AND, OR, XOR, NOT, left shift and right shift.

O(1) · O(1) space
Bit Masks
▶ viz

Represent a set of up to 64 booleans as one integer so that set operations become single bitwise instructions.

O(1) · O(1) space
Set, Clear, Toggle & Test a Bit
▶ viz

The four single-bit primitives: set with OR, clear with AND-NOT, toggle with XOR, test with AND on a shifted 1.

O(1) · O(1) space
Count Set Bits (Popcount)
▶ viz

Count the 1-bits of an integer with Kernighan's loop, a byte lookup table, a hardware popcount, or a DP over all numbers up to n.

O(w) · O(1) space
Power-of-Two Tricks
▶ viz

Test for powers of two with n & (n-1), isolate the lowest set bit with n & -n, and round up to the next power of two with shift-or smearing.

O(1) · O(1) space
Subset Generation with Bitmasks
▶ viz

Enumerate every subset of n items by counting masks from 0 to 2^n - 1, and every submask of a mask with s = (s - 1) & mask.

O(3^n) · O(2^n) space
XOR Patterns
▶ viz

Exploit XOR's self-cancelling property to find unpaired elements, missing numbers, swap without a temporary, and answer range-XOR queries.

O(n) · O(1) space