Recap — Bit Tricks Worth Memorizing

# Bit Tricks Worth Memorizing Bit manipulation is a small but high-leverage topic. A handful of tricks solve specific interview problems elegantly. ## The operations | Operator | Meaning | |---|---| | `&` | AND (1 if both bits 1) | | `\|` | OR (1 if either bit 1) | | `^` | XOR (1 if bits differ) | | `~` | NOT (flip all bits) | | ` >` | Right shift (divide by 2, floor) | ## The XOR magic XOR has wonderful algebraic properties: - `x ^ 0 = x` (XOR with 0 is identity) - `x ^ x = 0` (XOR with self is 0) - `x ^ y ^ x = y` (cancellation) - Commutative and associative ### Problem: Single number "Array where every element appears twice except one. Find the singleton." ```python def single_number(nums): result = 0 for n in nums: result ^= n return result ``` XOR all elements. Pairs cancel; the singleton remains. O(N) time, O(1) space. Magical. ### Problem: Missing number "Array contains 0..N with one missing." ```python def missing(nums): result = len(nums) for i, n in enumerate(nums): result ^= i ^ n return result ``` XOR all indices and values; the missing index/value pair leaves it as the answer. ## Bit counting and checking ### Count set bits (Hamming weight) ```python def count_bits(n): count = 0 while n: count += n & 1 # check lowest bit n >>= 1 return count ``` Or Python: `bin(n).count('1')`. ### Brian Kernighan's algorithm ```python def count_bits(n): count = 0 while n: n &= n - 1 # removes lowest set bit count += 1 return count ``` O(number of set bits), often faster than naive. ### Check if power of 2 ```python def is_power_of_two(n): return n > 0 and (n & (n - 1)) == 0 ``` Powers of 2 have exactly one set bit. `n & (n-1)` clears the lowest set bit; if result is 0, only one was set. ## Bit manipulation tricks (memorize) ### Get/set/clear/toggle k-th bit ```python # Get k-th bit (0-indexed from right) bit = (n >> k) & 1 # Set k-th bit n |= (1 << k) # Clear k-th bit n &= ~(1 << k) # Toggle k-th bit n ^= (1 << k) ``` ### Check if k-th bit is set ```python if n & (1 << k): ... ``` ### Lowest set bit ```python lowest = n & -n # gives a number with only the lowest set bit of n ``` ### Strip lowest set bit ```python n &= n - 1 ``` ## Subsets via bitmask Generate all subsets of an N-element set (N small, say ≤ 20): ```python def subsets(nums): n = len(nums) result = [] for mask in range(1 << n): subset = [nums[i] for i in range(n) if mask & (1 << i)] result.append(subset) return result ``` Each integer from 0 to 2ᴺ-1 represents one subset; bit i indicates whether nums[i] is included. Used in bitmask DP for small-N problems. ## XOR for ranges XOR of 1 to N: - N % 4 == 0: result = N - N % 4 == 1: result = 1 - N % 4 == 2: result = N + 1 - N % 4 == 3: result = 0 Useful in some problems; not necessary to memorize but handy. ## When bit tricks help in interviews - "Find the one that appears once" → XOR all. - "Count bits / Hamming distance" → Kernighan. - "Power of 2" → `n & (n-1) == 0`. - "Generate all subsets, N ≤ 20" → bitmask enumeration. - "Optimize state" → bitmask DP for small sets. ## Common bit-manipulation mistakes 1. **Operator precedence.** `a & b == 0` parses as `a & (b == 0)`. Use parens: `(a & b) == 0`. 2. **Confusing AND/OR/XOR.** XOR is "difference"; AND is "both"; OR is "either". 3. **Forgetting Python's arbitrary precision.** Negative numbers behave differently than in C/Java. 4. **Using bitwise OR when you meant `or`.** `|` is bitwise; `or` is logical. ## Takeaway Bit ops: & | ^ ~ >. XOR for pairing/canceling (single number, missing). Brian Kernighan's for counting bits. `n & (n-1) == 0` for power of 2. Bitmask enumeration for subsets (N ≤ 20). Small toolkit; high leverage when problems call for it.