|
This is absolutely true!
I didn't mention that, because I thought it was obvious.
But you are right - maybe it is not quite obvious for the OP, I should mention this fact.
Thanks,
Nuri
|
|
|
|
|
Aescleal wrote: Pointers need not apply
Not necessarily: swapping two pointers can be achieved by add/subtract if reinterpreted as integers of the appropriate size.
Don't think to pointer as "addresses" and to integer as "numbers".
Think in term of "sequence of bits".
The triple xor (as well as the add subtract) is just a mechanism that mix-up the bits so that the ones that were on a place appear to the other and vice-versa.
What the bit are used to represent what is indifferent.
The important thing is that +- (as well of ^) are not the overloaded specific for the particular type, but just the integer ones.
The only constrain is that the integer size (in bits) must be the same as the swapping type.
2 bugs found.
> recompile ...
65534 bugs found.
|
|
|
|
|
I don't think of pointers as addresses - they're variables that store addresses. The problem with add'em substract'em with pointers is either your code ends up with either loads of casts OR spurious zeros:
x += (y - 0);
Which may or may not be bad depending on your point of view. Personally I'd just use std::swap and say sod the efficiency unless someone can show me in a profiler that it's too slow.
Cheers,
ash
|
|
|
|
|
I prefer the XOR swap, it's more symmetric and elegant.
Cheers,
विक्रम (Got my troika of CCCs!)
"cant stand heat myself. As soon as its near 90`F I seriously start to loose interest in doing much." - fat_boy.
"Finally we agree, a little warming will be good if it makes you shut the f*** up about it." - Tim Craig.
|
|
|
|
|
If you're using C the various tricks other people have shown you will work, well, the XOR trick will, the add'em subtract'em one won't in all cases (you can't add two pointers although you can subtract them but can't use -=).
Having said that I wouldn't bother too much unless it's an accademic exercise. Years ago when I worked in the games industry there were loads of tricks like this one which were meant to save clock cycles. However when, after loads of micro-optimisations like this one, someone actually did any timings there didn't turn out to be a lot of difference.
Cheers,
Ash
|
|
|
|
|
I've been asked this one in an interview.
I wasn't aware of the XOR swap at the time and I think I used a temp variable in my answer.
I don't think I got an offer from that interview.
Pete
|
|
|
|
|
I have been a couple of times as well - I'm a bit wary of taking any job that needs that sort of low level bit fiddling though. A good one to fire back at the interviewer is "I'll show you the C, you show me the boolean algebra proof." It's a good test of what the interviewer is like.
Cheers,
Ash
|
|
|
|
|
lgmanuel wrote: am trying to swap the values of 'x' and 'y' without using a temporary storage like 'z'..
why ?
IMO, other than the fact that it uses a small "hack", there is no reason to use that in 2010. (or as a stupid interview question).
Watched code never compiles.
|
|
|
|
|
consider this:
template<class A>
void xswap(A& a, A& b)
{
for(size_t i=0; i<sizeof(a); ++i)
{
((char*)&a)[i] ^= ((char*)&b)[i];
((char*)&b)[i] ^= ((char*)&a)[i];
((char*)&a)[i] ^= ((char*)&b)[i];
}
}
This works even if A is a class one gigabyte wide, without allocate an extra gigabyte.
2 bugs found.
> recompile ...
65534 bugs found.
|
|
|
|
|
...and who would ever handle such monster objects by value?
|
|
|
|
|
Depends on what the object represent: may be transfer buffers, one of which is shared with a DMA or another process.
"Swap" merely means exchange the data visibility between devices, or processors.
And since they are physically bounded to a device, cannot be swapped by reference (swapping the respective pointers).
With less dimensions (typically, up to 4K or 9K), this exchanges are typically operated between the switch processors and the route processors of routers.
Of course, is not something to be abused, but may have its own specific application.
2 bugs found.
> recompile ...
65534 bugs found.
|
|
|
|
|
He doesn't. Note the signature: "xswap(A& a". But there are a number of flaws in handling things this way. For starters, the Visual C++ compiler (and I presume everyone else will also be in this category) compiles two versions for xswap, even if the only difference is the size of the array, so
int a[1024], b[1024], c[2048], d[2048];
xswap(a, b); xswap(c, d);
produces two copies of xswap. But let's not stop there. The assembly output for the xor version is horrible. I didn't check the + and - version above, but it will probably be just as bad. Visual C++ (and presumably other compilers also) does what looks like the right thing if you use a simple temporary, namely something like this:
mov eax, [current ptr for a]
mov edx, [current ptr for b]
mov [current ptr for b], eax
mov [current ptr for a], edx
Temporaries are definitely the way to go. They're more susceptible to compiler optimizations such as coalescing, and if you prefer, some style of XMM hand optimization. I see pxor has the option for an m128 argument, so maybe there's something there. I'm not even sure why this would be an interview question. Maybe a better interview question is: In how many ways is the xor solution a bad idea?
|
|
|
|
|
I was not referring to the parameter passing, but to the need for swapping gigabytes of data in-place instead of swapping pointers to buffers, which seems like the most obvious choice in most cases.
You make very good points in your post. Thanks for that.
|
|
|
|
|
i think its a homework question.
|
|
|
|
|
Using Ruby:
x, y = y, x
Try not to take life to seriously.
When all is done no one gets out alive anyway.
|
|
|
|
|
Use the processor registers. No temp variable involved. Use assembly language of your choice.
Fast! 4 CPU instructions w/4 memory waits & you're done!
int x = 150;
int y = 45;
asm{
LDA x;
LDB y;
STA y;
STB x;
}
Using XOR, do it 3 times slower...
11 CPU instructions w/7 memory waits
int x = 150;
int y = 45;
x ^= y;
y ^= x;
x ^= y;
#DEFINE B 1
int x = 150;
int y = 45;
asm{
LDA x;
XOR y;
STA x;
STA B;
LDA y;
XOR B;
STA y;
STA B;
LDA x;
XOR B;
STA x;
}
Otherwise, this other SLOW method...
12 CPU instructions w/6 memory waits
x += y;
y = x - y;
x -= y;
#DEFINE B 1
int x = 150;
int y = 45;
asm{
LDA x;
LDB y;
ADA B;
STA x;
CMB;
INB;
ADA B;
STA y;
CMA;
INA;
ADA x;
STA x;
}
Notes for the unknowing:
Operations on registers are much faster than memory access
Negating a number is two's complement
Two's complement is one's complement +1
One's complement reverses (NOTs) all bits
Who loves Assembler???
No JITCHIT either.
Gary
|
|
|
|
|
Is this in the "Homework help" section? the only time i've ever needed to do this was CompSci 221. haha.
|
|
|
|
|
These kinds of interview questions are rather silly. Now really: what does it prove or show? Maybe that you know how to perform the swap using some weird trick, but as far as your abilities i.t.o. software design it shows nought.
It will not work on strings, anyway.
|
|
|
|
|
int x = 450;
int y = 45;
Console.WriteLine("X = " + y);
Console.WriteLine("Y = " + x);
If you ask me, this fulfils the spec.
Edit: oh and this works with strings, numbers, pointers (well maybe not if it's C#), or any datatype at all really.
Ninja (the Nerd)
Confused? You will be...
|
|
|
|
|
You should be aware of the XCHG assembler instruction which will exchange two values, uses 3 cpu clocks. Your optimizations will, in some cases, use 3x more CPU clocks, larger binary and unreadable code.
|
|
|
|
|
<joke>
to avoid using temporary storage - i would consider showing the user two boxes, and asking them to swap the numbers for me. this is safe for strings or XML or whatever. if the user chooses to use Notepad or something, it doesn't bother me, but i know that my code executes as fast as possible and is bug-free because i am using natural techniques from nature.
microsoft does this when you have to change your password. it shows you three text boxes. the first is your old password, and the next two are your new password. the code first checks that the new password matches the new new password, and then swaps the new new password for the old password.
works seamless every time
|
|
|
|
|
x^=y;
y^=x;
x^=y;
Yes, it's cute, but it's faster to use a temporary. The xor method is only useful if you're doing it in assembly language and you don't have a free register or a temporary memory location.
ken@kasajian.com / www.kasajian.com
|
|
|
|
|
int x=150;
int y=45;
x=x+y;(195)
y=x-y;(150)
x=x-y;(45)
|
|
|
|
|
x = 15
y =13
x=x + y (15 + 13) = 28
y = x- y (28-13) = 15
x = x-y(28-15)
x = 13
Hence x=13;
y=15.
jigar sheth
|
|
|
|
|
hello guys.....im new to this. I wanna know that how can I get started with waveInOpen?? I am getting confused. What is the right path to get used to it. I just can not be happy taking samples from Internet, I must learn it but not taking it on the big picture, what is the right place.......plz plz help me.
|
|
|
|