Core Concepts

• 1Binary representation and two's complement: every integer is stored as a fixed-width binary number. Positive integers are stored in standard binary: 5 = 0101, 13 = 1101. Negative integers use two's complement: to negate N, flip all bits and add 1. So -1 = 11111...1 (all ones), -5 = flip(0101)+1 = 1010+1 = 1011. The key property: -N & N = N (the lowest set bit). Two's complement allows the same hardware adder circuit for both positive and negative arithmetic. In Python, integers have arbitrary precision so bit operations on negative numbers produce the mathematically correct two's complement result, but the binary representation is conceptually infinite ones extended to the left. In Java/C++, integers are fixed 32 or 64 bits and overflow wraps silently.
• 2Core bit operations — AND, OR, XOR, NOT, shifts: AND (&) keeps bits set in both operands — used to mask, clear bits, and test bits. OR (|) sets bits present in either operand — used to set bits and combine flags. XOR (^) flips bits that differ — the magic operator for cancellation (a ^ a = 0, a ^ 0 = a). NOT (~) flips all bits — in Python ~n = -(n+1) due to arbitrary precision. Left shift (<<) multiplies by 2 per shift: n << k = n * 2^k. Right shift (>>) divides by 2 per shift: for unsigned integers, fills with 0 (logical shift); for signed integers in Python/Java, fills with the sign bit (arithmetic shift). n >> 1 = n // 2. In Python, use n >> 31 to extract the sign bit of a 32-bit number.
• 3Get, set, clear, flip a single bit: four fundamental operations every bit manipulation interview expects. Get bit k: (n >> k) & 1 — shifts bit k to position 0, then AND with 1. Returns 1 if bit k is set, 0 otherwise. Set bit k: n | (1 << k) — OR with a mask that has only bit k set. Guarantees bit k is 1 regardless of its previous value. Clear bit k: n & ~(1 << k) — AND with a mask that has all bits set except bit k. Flip bit k: n ^ (1 << k) — XOR with a mask that has only bit k set; flips only that bit. These four operations are the building blocks for bitmask data structures, permission systems, and state machines.
• 4n & (n-1) clears the lowest set bit: subtracting 1 from n flips the lowest set bit from 1 to 0 and sets all lower bits to 1. ANDing with n cancels those lower bits and clears the original lowest set bit. Example: n=12=1100, n-1=1011, n&(n-1)=1000. Applications: (1) count set bits (Brian Kernighan): loop while n != 0, increment count, n = n & (n-1). Runs in exactly k iterations where k is the number of set bits. (2) Check if n is a power of 2: a power of 2 has exactly one set bit, so n & (n-1) == 0 (and n > 0). This is O(1) vs O(log n) for looping through bits. (3) Iterate over all subsets of a bitmask: start at mask, each iteration s = (s-1) & mask visits every non-empty subset.
• 5n & (-n) isolates the lowest set bit: -n in two's complement = ~n + 1. ANDing with n gives a mask with only the lowest set bit set. Example: n=12=1100, -n=0100 (in 4-bit), n&(-n)=0100. Applications: (1) find the position of the lowest set bit: bit_pos = int(math.log2(n & -n)). (2) Fenwick tree (Binary Indexed Tree): the parent of node i is i - (i & -i); the next node to update is i + (i & -i). This single operation defines the entire Fenwick tree traversal pattern. (3) Split a number into its lowest set bit and the remainder: remainder = n ^ (n & -n) or equivalently n & (n-1).
• 6XOR cancellation — single number and missing number: XOR has three critical properties: identity (a ^ 0 = a), self-inverse (a ^ a = 0), and commutativity/associativity. These combine to give: XOR of all elements in an array where every element appears twice except one gives the single unique element — all pairs cancel, leaving only the singleton. Finding missing number in [0..n]: XOR all indices 0..n with all elements; paired values cancel, leaving the missing number. This is O(n) time and O(1) space, superior to the sum formula n*(n+1)/2 - sum(nums) because it avoids potential integer overflow for large n and works with arbitrary value ranges.
• 7Brian Kernighan popcount and DP popcount: popcount (population count, Hamming weight) counts the number of set bits. Brian Kernighan method: while n: count += 1; n &= n-1. Runs in O(k) where k is the number of set bits — optimal for sparse numbers. Built-in: bin(n).count('1') in Python, Integer.bitCount(n) in Java, __builtin_popcount(n) in C++. DP method for counting bits for ALL numbers 0..n (LC 338): dp[i] = dp[i >> 1] + (i & 1). Intuition: i >> 1 is i with the last bit removed (already computed), plus 1 if the last bit of i is set. This fills the entire dp array in O(n) with a single pass. For base-2 digit DP patterns, understanding popcount is essential.
• 8Bitmask DP for subset enumeration: when the state space consists of subsets of a small set (n ≤ 20), represent each subset as an integer bitmask. State transitions iterate over subsets using the n & (n-1) trick. Classic pattern: dp[mask] = best value achievable using exactly the elements in mask. Example — Traveling Salesman Problem (TSP): dp[mask][i] = minimum cost to visit all cities in mask, ending at city i. Transition: dp[mask][i] = min over j in mask{i} of dp[mask ^ (1<<i)][j] + dist[j][i]. Total states: 2^n * n, transitions: O(n) per state → O(n² * 2^n) total. For n=20 this is ~20 million states — tractable. Iterating over all subsets of a mask (for s in subset enumeration): start s = mask, then s = (s-1) & mask until s == 0. Time O(3^n) over all masks — the three-exponential bound comes from each bit being in one of three states: not in mask, in mask but not in subset, in both.
• 9Bit tricks: swap, power of 2, arithmetic: swap without temp variable using XOR: a ^= b; b ^= a; a ^= b. Pitfall: never use this when a and b refer to the same memory location — a ^= b sets a to 0 and data is lost. Check power of 2: n > 0 and (n & (n-1)) == 0. Round up to next power of 2: n-=1; n|=n>>1; n|=n>>2; n|=n>>4; n|=n>>8; n|=n>>16; n+=1. This propagates the highest set bit rightward then adds 1. Multiply by 2^k: n << k. Integer division by 2^k: n >> k (floor for non-negative; note Python's >> is arithmetic and gives floor division correctly for negatives too). Check if bit at position k is set: bool(n & (1 << k)). Count trailing zeros: len(bin(n & -n)) - 3 or equivalently (n & -n).bit_length() - 1.
• 10Find two non-repeating numbers in array of pairs: when two elements appear once and all others appear twice, XOR of all elements gives x = a ^ b (where a, b are the two unique elements). Since a != b, x != 0, so at least one bit differs. Find any set bit of x (e.g., the lowest: diff_bit = x & -x). Partition all elements into two groups based on whether this bit is set — a falls in one group, b in the other. XOR all elements in each group gives a and b respectively, because pairs still cancel within each group. Time O(n), Space O(1). This is the classic LC 260 solution and directly demonstrates the power of using bit structure to partition and cancel.
• 11Maximum XOR using a trie: finding the maximum XOR of two numbers in an array naively takes O(n²). With a binary trie built on 32-bit representations of all numbers, for each number we greedily choose the opposite bit at each trie level (prefer 1 ^ 0 = 1 over 1 ^ 1 = 0). This greedy traversal takes O(32) per number → O(32n) = O(n) total. The trie has at most 32n nodes. This same trie structure underlies the solution to LC 421 (Maximum XOR of Two Numbers in an Array) and extends to range XOR maximum queries.

Key Patterns & Templates