LeetCode Patterns Flashcards: Bit Manipulation, XOR Tricks, Masks, Powers of Two

XOR, or exclusive or, has three useful properties: any number XOR itself equals zero, any number XOR zero equals itself, and XOR is commutative and associative. To find the single number in an array where every other number appears twice, XOR all elements together. The duplicate pairs cancel out to zero, leaving only the single number. This runs in O of n time and O of one space. For the variant where one number appears once and all others appear three times, XOR alone does not work, and you need bit counting where you count the number of ones at each bit position modulo three.

A power of two in binary has exactly one bit set: 1, 10, 100, 1000, and so on. The number minus one flips all bits below the set bit and clears the set bit itself: 1000 minus one equals 0111. The bitwise AND of a power of two and itself minus one is always zero. So the check is: the number is greater than zero and the number AND the number minus one equals zero. This runs in O of one time. This trick works because only powers of two have a single set bit. Numbers that are not powers of two have multiple set bits, so their AND with themselves minus one is nonzero.

The Brian Kernighan algorithm repeatedly clears the lowest set bit using the operation n AND n minus one, counting how many times this operation is needed until n reaches zero. Each operation removes exactly one set bit, so the loop runs exactly k times where k is the number of set bits, which is more efficient than checking all 32 bits. For the Hamming distance problem, first XOR two numbers to get a result where set bits represent positions that differ, then count the set bits of the XOR result. Counting set bits is also called the population count or popcount.

Given an array containing n distinct numbers from zero to n with one missing, XOR all array elements together and XOR with all numbers from zero to n. Every number that is present cancels out because it appears in both the array and the range, leaving only the missing number. This uses O of one space. Alternatively, calculate the expected sum of zero through n using the formula n times n plus one divided by two, subtract the actual array sum, and the difference is the missing number. Both approaches run in O of n time, but the XOR approach avoids potential integer overflow with large sums.

A bit mask is an integer where each bit represents whether a corresponding element is included in a subset. For a set of n elements, an n-bit integer can represent any subset: bit at position i equals one means element i is included. Iterating from zero to two to the power of n minus one enumerates all possible subsets. To check if element i is in the mask, AND the mask with one shifted left by i. To add element i, OR the mask with one shifted left by i. To remove, AND with the complement.

To reverse the bits of a 32-bit integer, iterate through all 32 positions. At each step, extract the lowest bit of the input using AND with one, shift it left to its reversed position which is 31 minus the current position, OR it into the result, and right-shift the input by one to process the next bit. After 32 iterations, the result contains all bits in reversed positions. This runs in O of one time since the number of bits is fixed at 32. An optimized approach divides and conquers by swapping adjacent bits, then pairs of two, then groups of four, eight, and sixteen in five operations. ---