DEV Community

Discussion on: How can you swap two variables without using a third?

Collapse
 
theodesp profile image
Theofanis Despoudis • Edited

Tricky bit: It can cause integer overflow if x + y > int.MAX

Collapse
 
tux0r profile image
tux0r

Validity checks were not a part of the question. But yes, you are right.

Thread Thread
 
theodesp profile image
Theofanis Despoudis

That's the second step in becoming a computer scientist.

Thread Thread
 
lewiscowles1986 profile image
Lewis Cowles

limit x and y to 16 bit or store 32-bit numbers in 64-bit. max int for 64-bit signed or unsigned is twice that of it's 32-bit counterpart.

You cannot overcome size problem if it's expressed in bits. Only higher-order structures like arrays would enable that and then you are absolutely storing more than two variables (possibly more than one per entry if it's a pointer).

Thread Thread
 
theodesp profile image
Theofanis Despoudis • Edited

That defeats the purpose of doing that plus you are making a difficult work of complicating things. I suspect is better if you use a temp variable after all!

Thread Thread
 
lewiscowles1986 profile image
Lewis Cowles

I suspect it's better if you don't try to copy with only two memory areas, but if you're going to worry about overflowing, then doubling storage size is the least complex thing you could do, and compatible with various CPU operating modes.

Collapse
 
drbearhands profile image
DrBearhands • Edited

assuming cyclic overflows, i.e. INTMAX + 1 = INTMIN:
if INTMAX - y < x (equivalent to x + y > INTMAX without cycles)
then x + y = INTMIN + y - (INTMAX - x - 1)
ergo, rewriting the equations as
x' = x + y
y' = x' - y
x'' = x' - y'
we get:
x' = INTMIN + y - (INTMAX - x - 1)
y' = x' - y
y' = INTMIN - (INTMAX - x - 1)
y' = INTMIN + 1 - INTMAX + x
y' = x
x'' = INTMIN + y - (INTMAX - x - 1) - y'
x'' = INTMIN + y - (INTMAX - x - 1) - x
x'' = INTMIN + y - INTMAX + x + 1 - x
x'' = INTMIN + 1 + y - INTMAX
x'' = y

Overflows schmoverflows.

EDIT: Might be worth noting that this approach and the bitwise operator are essentially the same thing. Combine two things in a way that is reversible if you have either of the two originals.

Thread Thread
 
theodesp profile image
Theofanis Despoudis

Unfortunately that works in theory but in practice and most compilers do not guarantee that behavior. For example:

Java: Will back cycle to -2147483648
Javascript: will eventually print infinity if the value is too high
Go: Will not compile