Math & BitMedium

Bit Manipulation

Use bitwise operations (AND/OR/XOR/shift) for space-efficient O(1) tricks.

How it works

Bit manipulation operates directly on the binary representation of integers using operators: AND (&), OR (|), XOR (^), NOT (~), left shift (<<), right shift (>>). Key identities: n & (n-1) clears the lowest set bit (test if power of 2: n & (n-1) == 0). n & (-n) isolates the lowest set bit. a ^ a = 0, a ^ 0 = a (XOR cancels pairs). XOR is its own inverse and is commutative/associative. Applications: find the single number in an array of pairs (XOR all elements), count set bits (Brian Kernighan: count how many times n & (n-1) != 0), generate all subsets using bitmasks (iterate 0 to 2^n-1), swap without temp variable (a^=b; b^=a; a^=b).

Interactive Playground

a = 5 (101), b = 3 (011). Apply bitwise XOR operation.

Speed

When to use

Power of two check: n & (n-1) == 0
Single number in array of pairs (XOR)
Subset enumeration using bitmask

✅Tips

1Memorize: `n & (n-1)` removes the lowest set bit. `n & (-n)` isolates the lowest set bit.

2For subset enumeration: iterate `mask` from 0 to (1<<n)-1, bit j of mask = whether item j is included.

3Right shift by 1 = divide by 2. Left shift by 1 = multiply by 2. Use for fast even/odd check: `n & 1`.

4XOR all array elements to cancel pairs — the remaining value is the unique element.

❌Common Mistakes

!Operator precedence: `n & n - 1` is parsed as `n & (n - 1)` in most languages but double-check with parentheses.

!Arithmetic right shift vs logical right shift — in Java, `>>` is arithmetic, `>>>` is logical.

!Negative numbers in bit manipulation — two's complement makes `~n = -(n+1)`, which surprises many.

!Off-by-one in bitmask DP: n items need masks 0 through (1<<n)-1, so use `< (1<<n)` not `<= (1<<n)`.

💡 Key Insight:XOR is its own inverse: a ^ a = 0 and a ^ 0 = a. Use it to cancel pairs.

Solved Problems0

No solved problems yet.

Related Patterns

Math→