Bit Manipulation

Every integer your program touches is already sitting in memory as a sequence of bits, and a surprising number of "clever" interview problems boil down to noticing that fact. Bit manipulation is the practice of operating directly on those bits with the processor's native bitwise instructions — AND, OR, XOR, NOT, and the two shifts — instead of building auxiliary data structures like hash sets or arrays. Because these operations run in a single CPU cycle and require no extra memory, a good bit trick often turns an O(n) space solution into an O(1) space one without sacrificing time complexity.

The core operators

• AND (&) — a bit in the result is 1 only if both operands have a 1 there. Used to test or clear specific bits: n & 1 checks whether n is odd (its lowest bit is set).
• OR (|) — a bit is 1 if either operand has a 1 there. Used to set specific bits.
• XOR (^) — a bit is 1 if exactly one operand has a 1 there. XOR is the workhorse of this topic because of one property: identical values cancel out. Formally, x ^ x = 0 and x ^ 0 = x, and XOR is commutative and associative, so in a ^ b ^ a the two as annihilate each other regardless of order, leaving b. This is exactly how you find a "lonely" element among duplicates without a hash set.
• NOT (~) — flips every bit. Combined with two's-complement arithmetic, ~n equals -n - 1.
• Shifts (<<, >>) — x << k multiplies x by 2^k (shifting bits toward higher significance and filling with zeros), while x >> k divides by 2^k. Shifts are how you walk over individual bit positions one at a time: (n >> i) & 1 reads the i-th bit of n.

A few identities that solve most problems

• n & (n - 1) clears the lowest set bit of n. Repeating this until n becomes 0 counts the set bits, and checking whether n & (n - 1) == 0 tests whether n is a power of two.
• n & -n isolates the lowest set bit (because -n is ~n + 1 in two's complement, every bit below the lowest set bit flips to match n, and everything above cancels).
• n & 1 checks parity — 1 for odd, 0 for even — and is cheaper than n % 2.
• x ^ x = 0, x ^ 0 = x — the cancellation trick behind "find the unique element" problems.