Exchanging two integers with no scratch variable
Question
How can you swap the values of two integer variables a and b without using a third variable?
Short answer
Arithmetic: a = a + b; b = a - b; a = a - b;, or XOR: a ^= b; b ^= a; a ^= b;. After the first step a holds the combination, from which each original value can be recovered. The addition version can overflow, and both fail if a and b refer to the same memory (the value becomes ), so check for aliasing.
Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 7.1 Algorithms, 'Number swap', p.171; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solutionLessons behind this question
- Interest Rate Swaps: Mechanics, Valuation, and the Comparative-Advantage Argument
- Algorithms, Growth Rates, and Asymptotic Notation
- Quicksort and Randomized Quicksort
Start with a free lesson: Swaps is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.
Read it free