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).
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!
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.
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.
Good thing the question was specific to integers. With floating point arithmetic this wouldn't be guaranteed to work in all cases. Especially in Java 😭
This is probably the simplest case that shows the space vs time choice for optimisation. Here you are saving memory but have more operations. 3 arithmetic and 3 assignments. If you used an extra variable you still have 3 assignments but lose the 3 arithmetic but also have to add/remove the variable to from the stack.
JavaScript, by nature, stores all numbers as double-precision IEEE 754 floating point numbers. The 52 bits of the fractional portion is used to store integers. This results in 'maximum safe integer' of 253 - 1. Further complicating things is that JavaScript's bitwise operators only deal with the lowest 32 bits of JavaScript's 54-bit integers. So the bitwise approach will not work on big integers in JavaScript.
Java Web Developer with a passion for Spring and cloud computing. Know a thing or two about AWS. Trying to learn NodeJS lately with the help of TypeScript.
This was my solution as well. I honestly never thought about this problem seriously and went for a third variable every time. I'm taking capacity for granted. I learned my lesson. u.u
Sorting functions. So you can write something simple like
// at this point in the sort, we know we must
// swap x with some other value
if a[x] < a[y] {
swap(&a[x], &a[y])
} else {
swap(&a[x], &a[z]) // a[x] and a[z] may be the same value
}
The function usually gets inlined anyway (depending on your compiler) and if it starts with if x == y { return } then it just compiles to if x != y { /* swap x and y */ }
In fact, might as well use a temporary variable at that point if you're expecting for compiler optimizations :shrug:. At that point they'd just become temporary registers and wouldn't have anything in memory, and a single xchg call
x = x + y
y = x - y
x = x - y
Tricky bit: It can cause integer overflow if
x + y > int.MAXValidity checks were not a part of the question. But yes, you are right.
That's the second step in becoming a computer scientist.
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).
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!
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.
assuming cyclic overflows, i.e. INTMAX + 1 = INTMIN:
if
INTMAX - y < x(equivalent tox + y > INTMAXwithout cycles)then
x + y = INTMIN + y - (INTMAX - x - 1)ergo, rewriting the equations as
x' = x + yy' = x' - yx'' = x' - y'we get:
x' = INTMIN + y - (INTMAX - x - 1)y' = x' - yy' = INTMIN - (INTMAX - x - 1)y' = INTMIN + 1 - INTMAX + xy' = xx'' = INTMIN + y - (INTMAX - x - 1) - y'x'' = INTMIN + y - (INTMAX - x - 1) - xx'' = INTMIN + y - INTMAX + x + 1 - xx'' = INTMIN + 1 + y - INTMAXx'' = yOverflows 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.
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
Good thing the question was specific to integers. With floating point arithmetic this wouldn't be guaranteed to work in all cases. Especially in Java 😭
This is probably the simplest case that shows the space vs time choice for optimisation. Here you are saving memory but have more operations. 3 arithmetic and 3 assignments. If you used an extra variable you still have 3 assignments but lose the 3 arithmetic but also have to add/remove the variable to from the stack.
JavaScript, by nature, stores all numbers as double-precision IEEE 754 floating point numbers. The 52 bits of the fractional portion is used to store integers. This results in 'maximum safe integer' of 253 - 1. Further complicating things is that JavaScript's bitwise operators only deal with the lowest 32 bits of JavaScript's 54-bit integers. So the bitwise approach will not work on big integers in JavaScript.
This was my solution as well. I honestly never thought about this problem seriously and went for a third variable every time. I'm taking capacity for granted. I learned my lesson. u.u
Wait.. readability of your code is also important!
Sure, it is. That's when you modularize your code and make an inline method or macro out of this.
If that's the case, then why swap at all?
Sorting functions. So you can write something simple like
Which would be inefficient, thus not recommended.
The function usually gets inlined anyway (depending on your compiler) and if it starts with
if x == y { return }then it just compiles toif x != y { /* swap x and y */ }In fact, might as well use a temporary variable at that point if you're expecting for compiler optimizations :shrug:. At that point they'd just become temporary registers and wouldn't have anything in memory, and a single
xchgcallYou could just write the registers yourself then...
Can you please elaborate on that?
x = 1 + 1
y = 2 - 1
x = 2 - 1
Nope, still true.
Sorry perceived wrongly my mistake. Deleted the previous comment. But the possibility of overflow is still there in this method.