How do you rewrite the swap function without using a tmp variable in
the swap function????
int main()
{
int x = 3;
int y = 5;
// Passing by reference
cout << "Passed by reference, before" << endl;
cout << "x = " << x << " y = " << y << endl;
swap(x,y);
cout << "Passed by reference, after" << endl;
cout << "x = " << x << " y = " << y << endl;
return 0;
}
void swap(int &x, int &y)
{
int tmp;
tmp = x;
x = y;
y = tmp;
}
50  17266 
"Steve" <ng*****@my-deja.com> wrote... How do you rewrite the swap function without using a tmp variable in
the swap function????
There used to be a popular trick involving XORing the integers in
three steps, which allowed you to avoid having to define a temporary
storage, but it is much less clear than with a temporary.
int a = 42, b = 73;
b = a ^ b;
a = b ^ a;
b = a ^ b;
// here 'a' is 73, 'b' is 42.
However, it's better to rely on std::swap for that.
V
Steve 2004-06-22 : How do you rewrite the swap function without using a tmp variable in
the swap function????
By doing something which could be called cross-xoring, with operator ^=
I leave it as an exercise, since it is fun :-)
(Don't worry about the tmp: remember that auto variables can live in
registers)
Walter Tross
On Tue, 22 Jun 2004 00:15:43 GMT, Victor Bazarov <v.********@comAcast.net> wrote: There used to be a popular trick involving XORing the integers in
three steps, which allowed you to avoid having to define a temporary
storage, but it is much less clear than with a temporary.
int a = 42, b = 73;
b = a ^ b;
a = b ^ a;
b = a ^ b;
// here 'a' is 73, 'b' is 42.
Or one can use regular addition and substruction:
b = a + b;
a = b - a;
b = b - a;
--
Maxim Yegorushkin
Even easier way:
a = a + b;
b = a - b;
a = a - b;
ex:
initially: a = 3, b = 7
1 step: a = 10, b = 7
2 step: a = 10, b = 3
3 step: a = 7, b = 3
KISS
On Mon, 21 Jun 2004 16:50:27 -0700, Steve wrote: How do you rewrite the swap function without using a tmp variable in
the swap function????
void swap(int &x, int &y)
{
int tmp;
tmp = x;
x = y;
y = tmp;
}
For *this specific case* (well, any integer case, actually -- or even
boolean) there is a shortcut based on the bitwise-XOR (^) operator. In
general you're better off using a temporary, in all but the most
pathological cases, where you're better off operating on pointers.
Working it out is best left as an exercise, because this sounds like
homework.
--
Some say the Wired doesn't have political borders like the real world,
but there are far too many nonsense-spouting anarchists or idiots who
think that pranks are a revolution.
Steve wrote:
How do you rewrite the swap function without using a tmp variable in
the swap function????
You don't
There is no advantage in doing so.
The popular xor-trick failes if you
try to swap a variable with itself.
The other popular arithmetic tricks
fail, if over- or underflow occours.
So the best thing is: Use a temporary.
--
Karl Heinz Buchegger kb******@gascad.at
This code does the trick, (no temp variable in function swap). But
is it a cheat?
# include <iostream>
using namespace std;
int x = 3; // this are now visible in swap
int y = 5; // this are now visible in swap
int main()
{
// Passing by reference
cout << "Passed by reference, before" << endl;
cout << "x = " << x << " y = " << y << endl;
swap(x,y);
cout << "Passed by reference, after" << endl;
cout << "x = " << x << " y = " << y << endl;
return 0;
}
void swap(int &a, int &b)
{
x = a;
y = b;
}
Bill Reyn posted: This code does the trick, (no temp variable in function swap). But
is it a cheat?
No it doesn't. It's non-functional (The english term, not the C++ term!).
# include <iostream>
using namespace std;
int x = 3; // this are now visible in swap
int y = 5; // this are now visible in swap
int main()
{
// Passing by reference
cout << "Passed by reference, before" << endl;
cout << "x = " << x << " y = " << y << endl;
swap(x,y);
cout << "Passed by reference, after" << endl;
cout << "x = " << x << " y = " << y << endl;
return 0;
}
void swap(int &a, int &b)
{
x = a;
At this point:
x == 3
y = b;
At this point:
y == 5
}
Your code does nothing.
Even if some-one were to call swap(y,x) , it still wouldn't work.
-JKop
"Steve" <ng*****@my-deja.com> wrote in message
news:97**************************@posting.google.c om... How do you rewrite the swap function without using a tmp variable in
the swap function????
void swap(int &x, int &y)
{
int tmp;
tmp = x;
x = y;
y = tmp;
}
Here is the Risto's Variable Free Recursive Integer Swap(TM):
void swap( int &r,int &s )
{
if( r < s )
{
--s;
swap( r,s );
++r;
}
else if( r > s )
{
--r;
swap( r,s );
++s;
}
}
Here's another old one that a few people found amusing enough
to pass around as a joke:
void swap( Thing &leftHand,Thing &rightHand )
{
try
{
throw leftHand;
}
catch( Thing falling )
{
leftHand = rightHand;
rightHand = falling;
}
}
Enjoy!
- Risto -
The xor solution was really elegant. I would not have thought about it
and never knew it could be done this way.
X XOR Y XOR Y = X (assign in y variable, cancel out both Y)
X XOR Y XOR X = Y (assign in x variable, cancel out both X)
Thanks for the help.
In message <97**************************@posting.google.com >, Steve
<ng*****@my-deja.com> writes The xor solution was really elegant. I would not have thought about it
and never knew it could be done this way.
X XOR Y XOR Y = X (assign in y variable, cancel out both Y)
X XOR Y XOR X = Y (assign in x variable, cancel out both X)
And it DOESN'T WORK (no apologies for shouting) if X and Y are both
references to the same object. Don't do it!
--
Richard Herring
Maxim Yegorushkin wrote: On Tue, 22 Jun 2004 00:15:43 GMT, Victor Bazarov
<v.********@comAcast.net> wrote:
There used to be a popular trick involving XORing the integers in
three steps, which allowed you to avoid having to define a temporary
storage, but it is much less clear than with a temporary.
int a = 42, b = 73;
b = a ^ b;
a = b ^ a;
b = a ^ b;
// here 'a' is 73, 'b' is 42.
Or one can use regular addition and substruction:
b = a + b;
a = b - a;
b = b - a;
Try it with 'a' and 'b' close to INT_MAX.
V
"Victor Bazarov" <v.********@comAcast.net> skrev i en meddelelse
news:PSKBc.91321$0y.55705@attbi_s03... "Steve" <ng*****@my-deja.com> wrote... How do you rewrite the swap function without using a tmp variable in
the swap function????
There used to be a popular trick involving XORing the integers in
three steps, which allowed you to avoid having to define a temporary
storage, but it is much less clear than with a temporary.
int a = 42, b = 73;
b = a ^ b;
a = b ^ a;
b = a ^ b;
// here 'a' is 73, 'b' is 42.
However, it's better to rely on std::swap for that.
Very clever! I just tested it:
int i(42);
victors_swap(i,9);
;-)
V
"Steve" <ng*****@my-deja.com> skrev i en meddelelse
news:97**************************@posting.google.c om... How do you rewrite the swap function without using a tmp variable in
the swap function????
int main()
{
int x = 3;
int y = 5;
// Passing by reference
cout << "Passed by reference, before" << endl;
cout << "x = " << x << " y = " << y << endl;
swap(x,y);
cout << "Passed by reference, after" << endl;
cout << "x = " << x << " y = " << y << endl;
return 0;
}
void swap(int &x, int &y)
{
int tmp;
tmp = x;
x = y;
y = tmp;
}
For integers, pointers and many other built-in types, theswap function
should just use a temporary. For more complex objects (e.g. std::string), it
can often be an advantage to do a memberwise swap. Actually, this is the way
it must be implemented if swap should have a nothrow guarantee (and it
should!).
/Peter
Risto Lankinen posted: void swap( Thing &leftHand,Thing &rightHand )
{
try
{
throw leftHand;
}
catch( Thing falling )
{
leftHand = rightHand;
rightHand = falling;
}
}
That one really made me laugh!!
-JKop
Richard Herring wrote: In message <97**************************@posting.google.com >, Steve
<ng*****@my-deja.com> writes
The xor solution was really elegant. I would not have thought about it
and never knew it could be done this way.
X XOR Y XOR Y = X (assign in y variable, cancel out both Y)
X XOR Y XOR X = Y (assign in x variable, cancel out both X)
And it DOESN'T WORK (no apologies for shouting) if X and Y are both
references to the same object. Don't do it!
That's simple enough to fix:
void xor_swap(int &a, int &b)
{
if (a != b)
{
b = a ^ b;
a = b ^ a;
b = a ^ b;
}
}
There's still no good reason to do it, of course.
--
Mike Smith
Richard Herring <ju**@[127.0.0.1]> wrote in message news:<1m**************@baesystems.com>... In message <97**************************@posting.google.com >, Steve
<ng*****@my-deja.com> writesThe xor solution was really elegant. I would not have thought about it
and never knew it could be done this way.
X XOR Y XOR Y = X (assign in y variable, cancel out both Y)
X XOR Y XOR X = Y (assign in x variable, cancel out both X)
And it DOESN'T WORK (no apologies for shouting) if X and Y are both
references to the same object. Don't do it!
Well... You *could* add a self-assignment guard.
Sometimes coders find themselves working on extremely limited hardware.
Like a smoke detector or something. And every variable is taking up
the very limited RAM that was only allowed by having an arm-wrestling
match with the comptroller and the accountant.
Socks And it DOESN'T WORK (no apologies for shouting) if X and Y are both references to the same object. Don't do it!
Well... You *could* add a self-assignment guard.
Sometimes coders find themselves working on extremely limited hardware.
Like a smoke detector or something. And every variable is taking up
the very limited RAM that was only allowed by having an arm-wrestling
match with the comptroller and the accountant.
Socks
Hmmm, seeems to me that adding the code to guard against swapping the same
variable would take more RAM than a temporary variable itself would take.
My guess is this was a homework question. (I had that question as an
extra-credit question in one of my programming classes.) I doubt there's
ever really a good reason to not use a temporary integer variable for
swapping. (And of course, using the std::swap function is even better, if
you're not toooo pressed for space.)
-Howard
Howard wrote: I doubt there's
ever really a good reason to not use a temporary integer variable for
swapping.
Small footprint embedded systems would be a good place/reason.
"Julie" <ju***@nospam.com> wrote in message
news:40***************@nospam.com... Howard wrote: I doubt there's
ever really a good reason to not use a temporary integer variable for
swapping.
Small footprint embedded systems would be a good place/reason.
You don't have room for one integer? (Then you also don't have room for the
code to guard aginst swapping a number with itself, do you?) Anyone out
there ACTUALLY had to write a program where there wasn't room for a single
temporary integer value??? I seriously doubt it. (And don't embedded
systems ever use registers for this? That's what I usually use when I write
in assembler, since it's faster than using RAM.)
-Howard
Howard wrote:
"Julie" <ju***@nospam.com> wrote in message
news:40***************@nospam.com... Howard wrote: I doubt there's
ever really a good reason to not use a temporary integer variable for
swapping.
Small footprint embedded systems would be a good place/reason.
You don't have room for one integer? (Then you also don't have room for the
code to guard aginst swapping a number with itself, do you?) Anyone out
there ACTUALLY had to write a program where there wasn't room for a single
temporary integer value??? I seriously doubt it. (And don't embedded
systems ever use registers for this? That's what I usually use when I write
in assembler, since it's faster than using RAM.)
-Howard
Talk to Ed Nisley -- he regularly talks about bit counting in embedded systems
in his "Embedded Space" forum in DDJ.
Guarding against self-swapping could be an (assumed) precondition and not
included in the code.
Just trying to think outside of the box here, and not limiting it to a 'there
is no good reason to do it' mentality. pu*********@hotmail.com 2004-06-22 : Richard Herring <ju**@[127.0.0.1]> wrote in message news:<1m**************@baesystems.com>... In message <97**************************@posting.google.com >, Steve
<ng*****@my-deja.com> writesThe xor solution was really elegant. I would not have thought about it
and never knew it could be done this way.
X XOR Y XOR Y = X (assign in y variable, cancel out both Y)
X XOR Y XOR X = Y (assign in x variable, cancel out both X)
And it DOESN'T WORK (no apologies for shouting) if X and Y are both
references to the same object. Don't do it!
Well... You *could* add a self-assignment guard.
Sometimes coders find themselves working on extremely limited hardware.
Like a smoke detector or something. And every variable is taking up
the very limited RAM that was only allowed by having an arm-wrestling
match with the comptroller and the accountant.
It seems like nobody is taking in account the fact that the temporary
variable of a simple swap will most likely be a register, and this is very
likely to be true also when swapping classes member by member.
Walter Tross
"Walter Tross" <wa****@waltertross.com> wrote in message > > Sometimes
coders find themselves working on extremely limited hardware. Like a smoke detector or something. And every variable is taking up
the very limited RAM that was only allowed by having an arm-wrestling
match with the comptroller and the accountant.
It seems like nobody is taking in account the fact that the temporary
variable of a simple swap will most likely be a register, and this is very
likely to be true also when swapping classes member by member.
Walter Tross
This is true. However I can imagine the situation when you do not have that
register, because the remaining registers hold other importand data :)
Fortunately, some micros implement swapping in single instruction (similarly
to x86's XCHG).
Roman
> > You don't have room for one integer? (Then you also don't have room for the code to guard aginst swapping a number with itself, do you?) Anyone
out there ACTUALLY had to write a program where there wasn't room for a
single temporary integer value???
Guarding against self-swapping could be an (assumed) precondition and not
included in the code.
Unless the swap function was being used in some odd situation where
there was no possibility of the two variables having the same value,
you would end up doing the comparison yourself prior to the function
call anyway (or at least you SHOULD, in which case you would have to
have room for the temporary integer.) As *unlikely* as it may be that
the parameters wouldn't have the same values, unless it is
*impossible* (assuming there are no bugs elsewhere in your program of
course,) it would bad programming etiquette to do the swap without the
comparison. It sounds to me like this question is nothing more than
programming trivia anyway.
-Brandon
<pu*********@hotmail.com> wrote in message
news:c7**************************@posting.google.c om...
1) Well... You *could* add a self-assignment guard.
2) Sometimes coders find themselves working on extremely limited hardware.
Aren't 1) and 2) mutually exclusive, especially when the
alternative (of using a temp) is typically going to be smaller
than 1) in size anyway?!?
- Risto -
Howard wrote: You don't have room for one integer? (Then you also don't have room for the
code to guard aginst swapping a number with itself, do you?) Anyone out
there ACTUALLY had to write a program where there wasn't room for a single
temporary integer value???
Yes. During system startup there may not be ANY local/stack storage
available because you haven't gotten far enough along for such things to
exist yet.
I've also listened to people who worked on hardware that didn't have
local storage whine about "arrogrant compiler writers".
Julie <ju***@nospam.com> wrote in message news:<40***************@nospam.com>... Howard wrote:
"Julie" <ju***@nospam.com> wrote in message
news:40***************@nospam.com... Howard wrote:
> I doubt there's
> ever really a good reason to not use a temporary integer variable for
> swapping.
Small footprint embedded systems would be a good place/reason.
You don't have room for one integer? (Then you also don't have room for the
code to guard aginst swapping a number with itself, do you?) Anyone out
there ACTUALLY had to write a program where there wasn't room for a single
temporary integer value??? I seriously doubt it. (And don't embedded
systems ever use registers for this? That's what I usually use when I write
in assembler, since it's faster than using RAM.)
-Howard
Talk to Ed Nisley -- he regularly talks about bit counting in embedded systems
in his "Embedded Space" forum in DDJ.
Are you sure there's even a difference in storage requirements?
Low-level optimizations like this are usually best left to the
compiler.
Here are two inline swap functions: swap1 which uses a temporary,
and swap2 which uses the XOR trick.
inline void swap1(int& a, int &b)
{
int temp = a;
a = b;
b = temp;
}
inline void swap2(int& a, int &b)
{
b = a ^ b;
a = b ^ a;
b = a ^ b;
}
For comparison, let's define a couple of test functions which
use swap1 and swap2, respectively, but are otherwise identical.
The conditional is there to ensure that swap can't be optimized
away entirely.
int Test1(int a, int b)
{
if (a > b) swap1(a, b);
return (a + 1) * b;
}
int Test2(int a, int b)
{
if (a > b) swap2(a, b);
return (a + 1) * b;
}
Here is the x86 assembly language output my compiler produces
for these two functions:
?Test1@@YAHHH@Z PROC NEAR
; Line 17
mov eax, DWORD PTR _a$[esp-4]
mov ecx, DWORD PTR _b$[esp-4]
cmp eax, ecx
jle SHORT Test$1
mov edx, eax
mov eax, ecx
mov ecx, edx
Test$1:
; Line 18
add eax, 1
imul eax, ecx
; Line 19
ret 0
?Test1@@YAHHH@Z ENDP
?Test2@@YAHHH@Z PROC NEAR
; Line 23
mov eax, DWORD PTR _a$[esp-4]
mov ecx, DWORD PTR _b$[esp-4]
cmp eax, ecx
jle SHORT Test1$1
xor ecx, eax
xor eax, ecx
xor ecx, eax
Test1$1:
; Line 24
add eax, 1
imul eax, ecx
; Line 25
ret 0
?Test2@@YAHHH@Z ENDP
They are identical except that the first uses three register MOV
and the second three register XOR instructions to do the swap.
Neither uses any memory, although the first uses an additional
register (which is already available).
Now let's consider another variation in which we remove the
condition:
int Trivial1(int a, int b)
{
swap1(a, b);
return (a + 1) * b;
}
int Trivial2(int a, int b)
{
swap2(a, b);
return (a + 1) * b;
}
And here's the assembly output:
?Trivial1@@YAHHH@Z PROC NEAR
; Line 30
mov eax, DWORD PTR _b$[esp-4]
add eax, 1
imul eax, DWORD PTR _a$[esp-4]
; Line 31
ret 0
?Trivial2@@YAHHH@Z PROC NEAR
; Line 35
mov ecx, DWORD PTR _a$[esp-4]
mov edx, DWORD PTR _b$[esp-4]
xor edx, ecx
xor ecx, edx
mov eax, ecx
xor eax, edx
; Line 36
add ecx, 1
imul eax, ecx
; Line 37
ret 0
?Trivial2@@YAHHH@Z ENDP
What's going on here? Well, in the first case, the compiler
was able to optimize away the swap entirely and just do the
equivalent of return (b + 1) * a.
In the second case, the use of the XOR trick obscured the
intent of the code so the compiler just had to follow the
instructions literally. This is a common problem with using
tricky, low-level optimizations in source code. Compilers
can optimize better using the "as-if" rule if the effect of
the code is straightforward.
Guarding against self-swapping could be an (assumed)
precondition and not included in the code.
This places a burden on the user of the function to understand
the restruction and perform the test his/herself if necessary.
It is an error waiting to happen.
Just trying to think outside of the box here, and not limiting
it to a 'there is no good reason to do it' mentality.
There's a natural tendency to be seduced by clever tricks that
seem to promise a tiny gain in efficiency. Given that, it seems
to me that "thinking outside the box" involves taking into
account other factors that may not be so obvious. Let's weigh
the pros and cons in this case, shall we?
Pros:
* May save one int of memory in rare cases (i.e., where
there are no available registers)
Cons:
* Obfuscates the source code.
* Is less general (e.g., doesn't work for UDTs).
* Intruduces potential obscure bugs due to self-swap.
* Undermines compiler optimizations.
It seems to me that in this case there really is no good
reason to do it. That's not a "mentality" but a considered
judgment.
Victor Bazarov wrote: Or one can use regular addition and substruction:
b = a + b;
a = b - a;
b = b - a;
Try it with 'a' and 'b' close to INT_MAX.
I tried doing so and it produced the expected result.
What was supposed to happen?
"Bill Seurer" <se****@us.ibm.com> wrote in message
news:cb***********@news.rchland.ibm.com... Howard wrote:
You don't have room for one integer? (Then you also don't have room for
the code to guard aginst swapping a number with itself, do you?) Anyone out
there ACTUALLY had to write a program where there wasn't room for a
single temporary integer value???
Yes. During system startup there may not be ANY local/stack storage
available because you haven't gotten far enough along for such things to
exist yet.
I've also listened to people who worked on hardware that didn't have
local storage whine about "arrogrant compiler writers".
If there's no local/stack storage, then what exactly would you perform the
swap on? The assumption was that we were trying to swap two integers
without using a third as a temporary. Where do the two integers being
swapped exist? I'm questioning when you might have a case where you have
two such integers needing to be swapped, but don't have room for that one
temporary integer (even in a register).
I'm also curious (now) as to what kind of assembly language doesn't allow
you to define any local data. Can't you define the data in the code? How
the heck are you supposed to accomplish anything in code if you can't have
any variables to work with? And what do you mean by "you haven't gotten far
enough along for such things to exist yet"? Is there some sequence of
operations in your hardware that allows code to execute without any data
until something happens that magically allows you to use data?
-Howard
Maxim Yegorushkin posted: Victor Bazarov wrote:
> Or one can use regular addition and substruction:
>
> b = a + b;
> a = b - a;
> b = b - a;
Try it with 'a' and 'b' close to INT_MAX.
I tried doing so and it produced the expected result.
What was supposed to happen?
Try this
unsigned int a = 2147483651;
unsigned int b = 3250783651;
b = a + b;
a = b - a;
b = b - a;
That's why you use a temp variable!
-JKop
Maxim Yegorushkin wrote: Victor Bazarov wrote:
Or one can use regular addition and substruction:
b = a + b;
a = b - a;
b = b - a;
Try it with 'a' and 'b' close to INT_MAX.
I tried doing so and it produced the expected result.
What was supposed to happen?
Overflow. Undefined behaviour.
Howard wrote: If there's no local/stack storage, then what exactly would you perform the
swap on?
Static storage.
The assumption was that we were trying to swap two integers
without using a third as a temporary. Where do the two integers being
swapped exist? I'm questioning when you might have a case where you have
two such integers needing to be swapped, but don't have room for that one
temporary integer (even in a register).
It's doubtful this particular case would come up. i was answering the
more general question about there being programs without "room" for
local variables.
I'm also curious (now) as to what kind of assembly language doesn't allow
you to define any local data. Can't you define the data in the code? How
the heck are you supposed to accomplish anything in code if you can't have
any variables to work with? And what do you mean by "you haven't gotten far
enough along for such things to exist yet"? Is there some sequence of
operations in your hardware that allows code to execute without any data
until something happens that magically allows you to use data?
At certain points as some hardware starts there isn't any stack space
from which to allocate. Honest. Think really-low-level BIOS if all you
are familiar with is PCs.
Victor Bazarov wrote:
Maxim Yegorushkin wrote: Victor Bazarov wrote:
Or one can use regular addition and substruction:
b = a + b;
a = b - a;
b = b - a;
Try it with 'a' and 'b' close to INT_MAX.
I tried doing so and it produced the expected result.
What was supposed to happen?
Overflow. Undefined behaviour.
On most architectures it works just fine. On those architectures, "try
it" gives the wrong answer.
--
Pete Becker
Dinkumware, Ltd. ( http://www.dinkumware.com)
Bill Seurer <se****@us.ibm.com> wrote in message news:<cb***********@news.rchland.ibm.com>... Howard wrote:
You don't have room for one integer? (Then you also don't have room for the
code to guard aginst swapping a number with itself, do you?) Anyone out
there ACTUALLY had to write a program where there wasn't room for a single
temporary integer value???
Yes. During system startup there may not be ANY local/stack storage
available because you haven't gotten far enough along for such things to
exist yet.
Please explain how it is possible for *any* C or C++ code to execute
under these circumstances. (Remember, everything is a function...)
Surely such startup code would be written in assembler.
I've also listened to people who worked on hardware that didn't have
local storage whine about "arrogrant compiler writers".
I wouldn't know, not having done this kind of programming, but it
seems reasonable that compiler writers would have to make (and document)
certain basic assumptions about the target execution environment.
When you say "no local storage," do you actually mean no RAM, only
registers? If so, that sounds like a pretty special circumstance where
one should expect to use assembly language.
Niklas Borson wrote: Bill Seurer <se****@us.ibm.com> wrote in message news:<cb***********@news.rchland.ibm.com>...I've also listened to people who worked on hardware that didn't have
local storage whine about "arrogrant compiler writers".
I wouldn't know, not having done this kind of programming, but it
seems reasonable that compiler writers would have to make (and document)
certain basic assumptions about the target execution environment.
When you say "no local storage," do you actually mean no RAM, only
registers? If so, that sounds like a pretty special circumstance where
one should expect to use assembly language.
The specific case I am thinking of was a guy who worked with a group
that didn't use a "high level language" but wanted to. He was griping
about how all the compilers made assumptions without asking "potential"
users what they need. I don't think he ever got what he wanted but he
sure was upset about it.
Niklas Borson wrote:
<snip basis> It seems to me that in this case there really is no good
reason to do it. That's not a "mentality" but a considered
judgment.
In your case, and *only* your case.
Re-read the thread, there are several responses which more or less state 'there
is no good reason to do it' -- which is an inappropriate blanket statment and
definitely inside the box mentality.
Use what is appropriate for a given situation (hardware, target, compiler,
etc.) -- period. If that means the xor trick, then use it, if not, then use
something else like std::swap or whatever is necessary _and_appropriate_.
With the exception of the blanket 'don't do it' statements, this thread has
been enlightening and informative.
The question on how to do the swapping without tmp variable was just
part of a question in a interview test that I went through.I,m not
trying to save/conserve any space or memory or doing anything funny,
anyway there is already a std::swap template available in c++.....
JKop wrote: > b = a + b;
> a = b - a;
> b = b - a;
Try it with 'a' and 'b' close to INT_MAX.
I tried doing so and it produced the expected result.
What was supposed to happen?
Try this
unsigned int a = 2147483651;
unsigned int b = 3250783651;
b = a + b;
a = b - a;
b = b - a;
On what platform? On x86 it works fine.
--
Maxim Yegorushkin
Pete Becker wrote: Overflow. Undefined behaviour.
On most architectures it works just fine. On those architectures, "try
it" gives the wrong answer.
I'd like to know about architectures where that code does not work. I'm curious if there are processors where addition/substruction processor command does not wrap result using modulo.
--
Maxim Yegorushkin
Maxim Yegorushkin wrote:
On what platform? On x86 it works fine.
Try
#include <iostream>
using namespace std;
int main()
{
double a = 0.00000001;
double b = 100000000.0;
cout << a << " " << b << endl;
b = a + b;
a = b - a;
b = b - a;
cout << b << " " << a << endl;
}
On my Windows machine the output is:
1e-008 1e+008
1.49012e-008 1e+008
--
Karl Heinz Buchegger kb******@gascad.at
Karl Heinz Buchegger wrote: Try
#include <iostream>
using namespace std;
int main()
{
double a = 0.00000001;
double b = 100000000.0;
cout << a << " " << b << endl;
b = a + b;
a = b - a;
b = b - a;
cout << b << " " << a << endl;
}
On my Windows machine the output is:
1e-008 1e+008
1.49012e-008 1e+008
I don't think this is a legitimate example here.
The topic is about integers, not doubles. They are rather disparate subjects.
Floating point arithmetics has limited precision. What you are doing here - adding/substracting disparately huge and small floating point numbers - is no way to go if you want to keep rounding errors at minimum.
--
Maxim Yegorushkin
Maxim Yegorushkin posted: Pete Becker wrote:
Overflow. Undefined behaviour.
On most architectures it works just fine. On those architectures, "try
it" gives the wrong answer.
I'd like to know about architectures where that code does not work. I'm
curious if there are processors where addition/substruction processor
command does not wrap result using modulo.
Post here what size your:
char
short
int
long
are, and I'll give you some numbers to try. Alternatively:
a = INT_MAX / 2;
b = INT_MAX / 2 + 48;
-JKop
JKop <NU**@NULL.NULL> wrote: Overflow. Undefined behaviour.
On most architectures it works just fine. On those architectures, "try
it" gives the wrong answer.
I'd like to know about architectures where that code does not work. I'm
curious if there are processors where addition/substruction processor
command does not wrap result using modulo.
Post here what size your:
I only have access to x86 platforms (linux/windows) these days.
char
1
short
2
int
4
long
4
are, and I'll give you some numbers to try. Alternatively:
a = INT_MAX / 2;
b = INT_MAX / 2 + 48;
I think there is nothing to try. On x86 equivalent assembly code looks like:
mov eax, [a]
mov edx, [b]
add eax, edx
sub edx, eax
sub eax, edx
mov [a], eax
mov [b], edx
which wraps the results of add/sub on modulo 2^32, so that it always gives the right answer.
--
Maxim Yegorushkin
"Peter Koch Larsen" <pk*****@mailme.dk> skrev i en meddelelse
news:ZN*******************@news000.worldonline.dk. ..
"Victor Bazarov" <v.********@comAcast.net> skrev i en meddelelse
news:PSKBc.91321$0y.55705@attbi_s03...
Very clever! I just tested it:
int i(42);
victors_swap(i,9);
Argh.... that should be swap(i,i), of course ;-((
Maxim Yegorushkin wrote: I think there is nothing to try. On x86 equivalent assembly code looks like:
mov eax, [a]
mov edx, [b]
add eax, edx
sub edx, eax
sub eax, edx
mov [a], eax
mov [b], edx
Sorry, the code is wrong (I was in a rush being waited by starving people heading for lunch ;) ).
which wraps the results of add/sub on modulo 2^32, so that it always gives the right answer.
But this is right.
--
Maxim Yegorushkin
Maxim Yegorushkin wrote:
Karl Heinz Buchegger wrote:
Try
#include <iostream>
using namespace std;
int main()
{
double a = 0.00000001;
double b = 100000000.0;
cout << a << " " << b << endl;
b = a + b;
a = b - a;
b = b - a;
cout << b << " " << a << endl;
}
On my Windows machine the output is:
1e-008 1e+008
1.49012e-008 1e+008
I don't think this is a legitimate example here.
The topic is about integers, not doubles.
The topic is to write a swap function without
using a temporary.
--
Karl Heinz Buchegger kb******@gascad.at
Karl Heinz Buchegger wrote:
The topic is about integers, not doubles.
The topic is to write a swap function without
using a temporary.
Ooops. Sorry.
The subject lines clearly states: integers
My fault
--
Karl Heinz Buchegger kb******@gascad.at
Julie <ju***@nospam.com> wrote in message news:<40***************@nospam.com>... Niklas Borson wrote:
<snip basis> It seems to me that in this case there really is no good
reason to do it. That's not a "mentality" but a considered
judgment.
In your case, and *only* your case.
By "this case" I was referring to the XOR trick for swapping
integers, not to any particular hardware platform or other
circumstance. I don't believe there's ever a good reason to
use the XOR trick in C++ for the reasons I gave (which you
snipped).
Re-read the thread, there are several responses which more
or less state 'there is no good reason to do it' -- which is an inappropriate
blanket statment and definitely inside the box mentality.
I agree with those responses. There is no reason to use this
particular trick in C++. It's clever. It's fun. But it has
no practical value.
I'm not saying one shouldn't care about performance, or that
one shouldn't write small, tight code. Even obscure tricks
like Duff's device can be justifiable in truly performance
critical code. But this particular trick has known risks and
essentially no practical value.
If you can provide a counter-example, I'd love to see it.
So far you've made assertions.
The counter-examples given by others have involved situations
(e.g., no stack or no storage at all) where one couldn't
really use C++ at all. In such cases, program in assembly,
and by all means use the XOR trick. Assembly language is the
right place for low-level optimizations such as this.
Use what is appropriate for a given situation (hardware, target, compiler,
etc.) -- period. If that means the xor trick, then use it, if not, then use
something else like std::swap or whatever is necessary _and_appropriate_.
Sure, I agree with that philosophy in general. In the case of
the xor trick, I don't believe there is any situation where it
is actually a good idea. Again, if you have an actual argument
to the contrary, please make it.
Niklas Borson wrote: Use what is appropriate for a given situation (hardware, target, compiler,
etc.) -- period. If that means the xor trick, then use it, if not, then use
something else like std::swap or whatever is necessary _and_appropriate_.
Sure, I agree with that philosophy in general. In the case of
the xor trick, I don't believe there is any situation where it
is actually a good idea. Again, if you have an actual argument
to the contrary, please make it.
I don't have an argument to the contrary, but that doesn't mean there isn't one
--
I guess I just prefer to look at things from outside of the box and avoid
blanket statements...
-end This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: raju |
last post by:
hi
can we compare two integers without using relational operators (== != <
<= > >=)
thanks
rajesh s
|
by: indrawati.yahya |
last post by:
OK, before you all stab me with your OT pitchfork, I just want to
mention that this question is indeed related to c.l.c++. My question
is, does the well-known method to swap two integers produce...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
| |
