Bit Manipulation
Practice & Revision
Bit Manipulation pattern recognition decision tree, cheat sheet, and Top 15 must-solve bitwise interview problems.
1. Introduction
This section serves as your comprehensive reference and practice guide for Bit Manipulation. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.
2. Bitwise Decision Tree
Use this flow chart to determine the correct bitwise strategy based on your problem:
3. Revision Cheat Sheet
Common Bitwise Operations & Masks
| Operation Goal | Bitwise Expression | How it Works | Complexity | |
|---|---|---|---|---|
| Odd/Even Check | x & 1 | Odd returns 1, Even returns 0. | O(1) | |
| Get i-th Bit | (x >> i) & 1 | Isolates index i and reads it. | O(1) | |
| Set i-th Bit | x \ | (1 << i) | Forces bit i to 1. | O(1) |
| Clear i-th Bit | x & ~(1 << i) | Forces bit i to 0. | O(1) | |
| Toggle i-th Bit | x ^ (1 << i) | Flips bit i. | O(1) | |
| Power of Two Check | x > 0 && (x & (x-1)) == 0 | Checks if exactly one bit is set. | O(1) | |
| Clear Lowest Set | x & (x - 1) | Flips the rightmost 1 to 0. | O(1) | |
| Isolate Lowest Set | x & -x | Keeps only the rightmost 1 set. | O(1) |
4. Top 15 Must-Solve Bit Manipulation Problems
5. Problem-Solving Framework
When coding Bitwise solutions, follow this 3-step checklist:
1. Leverage XOR Identities:
- In search problems containing duplicates, remember that XOR is commutative and associative. A ^ B ^ A = B. This cancels out pairs automatically.
2. Watch Shift Range Bounds:
- Remember that 1 << i triggers integer overflow when i >= 31 (in Java/C++). Always use 1L << i or 1LL << i for sets larger than 30 elements.
3. Double-Check Operator Precedence:
- Bitwise operations bind weaker than arithmetic comparisons. Always wrap masks in parentheses, e.g. if ((x & 1) == 0) instead of if (x & 1 == 0).
6. Quiz
Question 1: In 'Sum of Two Integers', how is addition calculated without standard + or - operators?
Answer: We calculate the sum without carries usinga ^ b, and compute the carries using (a & b) << 1. We repeat this process recursively until the carry term becomes 0.
Question 2: In 'Single Number III', why do we isolate the lowest set bit 'x & -x' of the aggregate XOR value?
Answer: The aggregate XOR value isA ^ B (the two unique numbers). Because they are unique, at least one bit must differ between them, resulting in a 1 in the XOR value. Isolating that lowest set bit allows us to divide the array into two groups: one where this bit is set, and one where it is not. This separates A and B into different groups, allowing us to find them using standard XOR cancellation in each group.
Question 3: What does the expression x & (x - 1) do in a power of two check?
Answer: It clears the rightmost set bit. If the number is a power of two (which has exactly one set bit), clearing it leaves0, confirming the property.
Question 4: True or False: Shift operations on 64-bit integers are faster than shift operations on 32-bit integers on 64-bit CPUs.
Answer: False. On modern 64-bit architectures, both run at identical register speeds (usually 1 clock cycle).Question 5: What is the result of ~(-1) (bitwise NOT of -1)?
Answer:0. In Two's Complement representation, -1 has all bits set to 1, so inverting it yields 0.