What is Bit Manipulation?
Bit manipulation works directly with the zeroes and ones inside an integer. Each bit can represent a small yes-or-no fact.
It helps to know binary place values and basic integer arithmetic. The short version is: use bit operations when the binary form contains a simpler pattern than the decimal number shows.
The Core Idea: Cancel Equal Bits
In Single Number [2,2,1], the two copies of 2 should disappear and leave 1. XOR gives us exactly that behavior.
Why?
Any value XOR itself is zero, and zero XOR a value returns that value.
So 2 XOR 2 XOR 1 becomes 0 XOR 1, which is 1.
It is like pairing identical socks. Every complete pair goes back into the drawer, and the one sock without a partner remains on the table.
How XOR Removes Pairs
The Rule You Keep True
After processing any prefix of the array, result equals the XOR of exactly that prefix.
Any completed pair inside the prefix has already cancelled to zero.
Different operations answer different bit questions:
- XOR toggles bits and cancels equal values.
- AND with a mask checks whether selected bits are set.
- OR with a mask turns selected bits on.
- Shifts move a bit into or out of a chosen position.
Counting Bits is the one that usually trips us up.
The clever recurrence bits[i] = bits[i >> 1] + (i & 1) looks mysterious until we say it plainly: remove the last binary digit, reuse the smaller answer, then add that last digit.
Picking the Right Shape
From Rule to Code
- Write down what each bit represents.
- Choose the operation whose truth table matches the required change.
- Process one value or bit position at a time.
- Keep the accumulated mask or result in one integer.
- Convert back to the requested answer only after the bit work is finished.
The Single Number scan visits every value once, so it takes O(n) time and O(1) extra space.
When to use it
- •The problem asks about individual binary digits, parity, masks, or powers of two.
- •Values appear in pairs and one unmatched value must be found.
- •A compact set of boolean flags can fit inside an integer.
- •The prompt expects constant extra space through bitwise operations.
How to identify it
- •Words such as bit, binary, XOR, set bit, mask, or power of two appear.
- •The input contains a cancellation pattern such as every value appearing twice except one.
- •Only yes-or-no state is needed for several small positions.
- •Arithmetic alone feels awkward but the binary representation has a clear rule.
Key insights
- →XOR returns zero for equal bits and leaves a bit unchanged when paired with zero.
- →Because XOR is associative and commutative, equal values cancel regardless of order.
- →A mask selects, sets, clears, or toggles chosen bit positions.
- →The expression `x & (x - 1)` removes the lowest set bit from `x`.
- →Bit operations work on fixed-width integer representations, so signed values need care.
Common mistakes
- 01Using logical operators such as `&&` when a bitwise operator such as `&` is required.
- 02Reading a binary string from left to right but numbering bit positions from the wrong end.
- 03Forgetting that JavaScript bitwise operators convert numbers to signed 32-bit integers.
- 04Using the XOR cancellation trick when values do not actually appear in matching pairs.
- 05Writing a complicated mask before stating which bit positions it is meant to select.