Bit Manipulation

Treat an integer as a row of bits (base 2). Bit i is worth 2**i; bit index 0 is the least-significant (rightmost) bit. bin(13) -> 0b1101 = 8 + 4 + 1. This covers non-negative integers.

Operators (per bit)

• AND & — 1 only if both bits are 1. 12 & 10 == 8.
• OR | — 1 if either bit is 1. 12 | 10 == 14.
• XOR ^ — 1 if the bits differ. 12 ^ 10 == 6.
• NOT ~ — flips every bit; in Python ~x == -(x + 1), so ~12 == -13.
• Left shift << — slide left, fill zeros; x << k == x * 2**k. 3 << 2 == 12. 1 << i = one bit set at index i.
• Right shift >> — slide right, drop low bits; x >> k == x // 2**k. 13 >> 1 == 6.

Single-bit recipes (i = bit index)

• Test: (x >> i) & 1 -> 0 or 1.
• Set: x | (1 << i).
• Clear: x & ~(1 << i).
• Toggle: x ^ (1 << i).
• Mnemonic: OR to set, AND-with-NOT to clear, XOR to toggle, shift-then-& 1 to test.

Key idioms

• x & (x - 1) clears the lowest set bit. Count set bits by looping until 0 (runs once per set bit); power of two = x > 0 and (x & (x - 1)) == 0.
• x & -x isolates the lowest set bit (its place value): 12 & -12 == 4.
• XOR facts: a ^ a == 0, a ^ 0 == a, commutative + associative. XOR-ing a whole list where every value pairs up except one leaves the unique value (r = 0; for n: r ^= n) — O(n) time, O(1) space, no hash set.

Bitmasks as subsets

• One int encodes a subset of up to ~n small items: bit i set means “item i in”.
• Iterate every subset: for mask in range(1 << n); membership is (mask >> i) & 1.
• 1 << n == 2**n total subsets (includes the empty mask 0). This powers subset / state-compression DP.

Python specifics

• Ints are arbitrary precision (no overflow, no fixed width), so ~x is negative.
• To emulate fixed 32-bit behavior, mask with & 0xFFFFFFFF: ~5 & 0xFFFFFFFF == 4294967290.

Pitfalls

• Precedence: <</>> bind looser than + but tighter than &/|/^, and == binds tighter than &. 1 << 2 + 1 == 8; x & 1 == 0 parses as x & (1 == 0). Parenthesize: (x & 1) == 0.
• Testing a bit needs the & 1; x >> i alone still carries higher bits.
• x & (x - 1) removes the lowest set bit; x & -x keeps only it — opposite jobs.
• Fixed-width assumptions (C/Java) need manual & 0xFFFFFFFF in Python.

Big-O

Word-sized ints are O(1) per op; on arbitrary-precision ints it is really O(w) in the bit width.