Bit Manipulation
Working directly on a number's binary representation with AND/OR/XOR/shifts — for O(1) tricks and memory-efficient state.
Try answering in your head first, then click a question to check the model answer.
Q1.Explain why `n & (n - 1)` clears the lowest set bit of n, and one use case for this trick.(show answer)
n - 1 flips all the bits from the lowest set bit of n down to bit 0 (that set bit becomes 0, and all the 0s below it become 1s). ANDing with the original n then zeroes out exactly that lowest set bit, since it's now 0 in n-1, while all higher bits (unchanged in n-1) stay the same. Use case: repeatedly applying this and counting iterations until n becomes 0 counts the number of set bits (Brian Kernighan's algorithm), in O(number of set bits) rather than checking all 32/64 bit positions individually.
Q2.How does XOR let you find the single unique number in an array where every other number appears exactly twice?(show answer)
XOR is commutative, associative, and x XOR x = 0, x XOR 0 = x. XORing every element together, every number that appears twice cancels itself out to 0 (regardless of order), leaving only the number that appears once XORed with 0 — which is itself. This solves the problem in O(n) time and O(1) space, without needing a hash set to track seen values.
Q3.Why is `x << 1` equivalent to multiplying x by 2, and `x >> 1` equivalent to integer division by 2?(show answer)
Binary place values work the same way decimal place values do, but base 2 instead of base 10 — shifting every bit one position to the left is equivalent to multiplying by the base (2), just as appending a 0 to a decimal number multiplies it by 10. Shifting right divides by 2 (discarding the remainder), the same logic in reverse. This is why bit shifts are often used as a fast alternative to multiplication/division by powers of two.
Q4.How would you check if a given integer is a power of two using bit manipulation?(show answer)
A power of two has exactly one bit set in its binary representation (e.g. 8 = 1000). Using the n & (n - 1) trick to clear the lowest set bit: if n is a power of two, clearing its one set bit leaves 0. So the check is n > 0 && (n & (n - 1)) == 0 — the n > 0 guard is needed because the identity would otherwise incorrectly also match n = 0.