Every integer your program touches is already 32 light switches in a row, and the machine can read or flip any of them in a single instruction. Bit operations are the six operators that work on those switches directly: AND, OR, XOR, NOT, and the two shifts. Used well, they pack 64 booleans into one machine word at an eighth of the memory, cancel duplicates out of an array without a hash set, and enumerate all 2ⁿ subsets of a collection with a plain counting loop.

Interviews love this topic because the tricks look like magic and decompose into two ideas: each operator's one-line truth table, and the two's complement encoding that decides what negative numbers look like. Both fit on this page.

Line up 13 = 1101 and 11 = 1011 and every operator is a column-by-column rule. AND keeps a 1 only where both have one: 13 & 11 = 1001 = 9. OR keeps a 1 where either does: 13 | 11 = 1111 = 15. Predict the third before reading on: XOR keeps a 1 only where the columns differ, so what is 13 ^ 11?

The columns disagree in the middle two places: 0110 = 6. Shifts move the whole row of switches: 13 << 2 = 52 multiplies by 4, and 13 >> 1 = 6 divides by 2 and floors. The last operator, NOT, flips every switch, and what it returns depends on the encoding: two's complement represents -x as "flip all bits, add 1", which makes -1 the all-ones pattern and gives the identity ~x = -x - 1. That encoding is why the tricks below work on negatives at all.

Three identities power most bit problems. First, n & (n - 1) deletes the lowest set bit: subtracting 1 flips the rightmost 1 and everything after it, so AND-ing with the original keeps all the higher bits and kills that one. Watch it on 12 = 1100: 12 & 11 = 1100 & 1011 = 1000 = 8. Second, n & -n isolates that same bit instead of deleting it: 12 & -12 = 4, straight from the two's complement negation. Third, XOR cancels pairs: x ^ x = 0 and x ^ 0 = x, and because XOR is commutative, order never matters.

That third identity is a whole solution by itself. Single Number hands you an array where every value appears twice except one. XOR everything together and the pairs annihilate, leaving the loner, in one pass and zero extra memory:

def single_number(nums: list[int]) -> int:
    result = 0

    for num in nums:
        # Pairs cancel: x ^ x = 0, and x ^ 0 = x
        result ^= num

    return result

How many 1 bits does a number hold? The obvious loop checks all 32 positions. Brian Kernighan's loop applies the delete-lowest-bit identity instead and runs once per set bit: 12 goes to 8 goes to 0, two iterations, two bits. A number with one set bit costs one iteration no matter where that bit lives.

def count_set_bits(n: int) -> int:
    count = 0

    while n != 0:
        # Clear the lowest set bit: one loop per 1 bit
        n &= n - 1
        count += 1

    return count

Counting Bits asks for the count of every number up to n at once, and a one-line recurrence beats running Kernighan n times: dp[i] = dp[i >> 1] + (i & 1), since shifting right drops only the last bit. And when you just need raw speed, modern CPUs count bits in hardware: C++20 exposes it as std::popcount.

You might think if (x & 1 == 0) checks for an even number. In C, C++, and Java, == binds tighter than &, so it evaluates x & (1 == 0), which is always 0, and the branch quietly never runs. The bitwise operators sit so low in the precedence table that the only safe habit is parentheses around every bit expression that meets a comparison.

The other ambushes are language-shaped. Java's >> drags the sign bit along (so negative stays negative) while >>> fills with zeros. JavaScript coerces every bitwise operand into a 32-bit signed integer, so numbers above 2,147,483,647 lose bits before the operator even runs. And a left shift only equals multiplication while the result still fits, since shifting into the sign bit turns a big number negative. The light-switch picture is honest about the switches and silent about the wiring, and the wiring is where these bugs live.

The XOR-cancellation family covers Single Number and Missing Number, where XOR-ing indices against values makes every matched pair vanish. Per-bit counting handles Single Number II: count how often each of the 32 positions is set across the array, take each count mod 3, and the unique number reassembles bit by bit. Bitwise AND of Numbers Range reduces to finding the common binary prefix of the two endpoints, because any differing bit gets zeroed somewhere in between.

The pattern with the longest reach is the bitmask as a set. Counting a mask from 0 to 2ⁿ - 1 enumerates every subset of n elements, an iterative cousin of backtracking's subset tree. Push it further and masks become dynamic programming states: dp[mask] records the best result over a whole set of visited items, which is how the traveling-salesman problem gets solved exactly for n ≤ 20.

Bit code is terse, which means its habits matter more than its line count:

Two checks first: why does n & (n - 1) delete exactly the lowest set bit, and what value survives when you XOR an array where everything but one element appears twice? The problems below start with the XOR family, then counting, then the trickier reconstructions: