muliplying without using a * operator! - Page 2

[Ancient Dragon]

How is x ^= y; y ^= x; x ^= y; unsafe when x and y are equally sized integers? Is there a problem with using xor for signed integers?

it has the same overflow problem that my template has.

Well, I wouldn't really use it, because I've never swapped integers in my life.

Are you still a student? If not, how long have you been programming? Swapping integers (and other data types) is a common thing in sorting algorithms.

As for swapping strings, there is a member function named 'swap' which tends to achieve the task in constant time.

probably implemented like this

void swap(std::string& s1, std::string& s2)
{
   std::string temp = s1;
   s1 = s2;
   s2 = temp;
}

I know of no other way to do it with std::strings.

[Ancient Dragon]

Without special case tests, the XOR swap is hopelessly broken.

How? my compiler has no problems with it. Of course you can't see the difference if x = y, but the code seems to work ok.

[Narue]

>but the code seems to work ok.
Perhaps my wording was poor. If a and b refer to the same object, the result will be 0, regardless of what the original value was. Sure, you may argue that this is an unlikely event, but I've seen it fairly often, especially in sorting algorithms.

*sigh* I tire of explaining this time and time again.

[Ancient Dragon]

>but the code seems to work ok.
Perhaps my wording was poor. If a and b refer to the same object, the result will be 0, regardless of what the original value was. Sure, you may argue that this is an unlikely event, but I've seen it fairly often, especially in sorting algorithms.

Oh you mean x ^= x?. I see your point about it not working when you want to swap the two values when they are both the same variable. swap function should never be called when the two variables are the same.

[Dave Sinkula]

Sometimes it may be more difficult to notice when you are swapping a variable with itself.

So let's see about the cool XOR swap.

• Won't work for pointers or floats.
• Won't work with self.
• Has syntax issues that may lead to the programmer to write UB code.
• Likely confuses and disables the optimizer.
• May be confusing to a new programmer.

What was an advantage?

[vegaseat]

>How is x ^= y; y ^= x; x ^= y; unsafe when x and y are equally sized integers?
Try it when x == y. Without special case tests, the XOR swap is hopelessly broken.

x == y works just swell, maybe just for the moment. I am trusting programmers like Treedog and so on they have the experience. So, the SWAP macro has received the Oakwood Club flush!
In Reality 201 they teach you that there are actually 27.3 different types of people.

[Narue]

>x == y works just swell
Yes, of course. We've established that my wording was poor. Try using the swap when x and y are the same variable and have a non-zero value.

>I am trusting programmers like Treedog
Who is Treedog? I haven't seen anyone by that name post in this thread, so if you're talking about an external resource, please provide a link.

[vegaseat]

>x == y works just swell
Yes, of course. We've established that my wording was poor. Try using the swap when x and y are the same variable and have a non-zero value.

>I am trusting programmers like Treedog
Who is Treedog? I haven't seen anyone by that name post in this thread, so if you're talking about an external resource, please provide a link.

Sorry, I meant DogTree, got him confused with TreeDog at the old Rock Bottom Brewery. Too much alcohol at times, a curse.

[Rashakil Fol]

Are you still a student? If not, how long have you been programming? Swapping integers (and other data types) is a common thing in sorting algorithms.

I am a student, and I've written most common sorting algorithms. Them being generic, I never end up swapping "integers", just some type named "T", via a third variable.

Swapping integers that are known to be integers (or unsigned integers, if signed integers actually do have problems) is just something I have not run into.

probably implemented like this

void swap(std::string& s1, std::string& s2)
{
   std::string temp = s1;
   s1 = s2;
   s2 = temp;
}

I know of no other way to do it with std::strings.

When implemented sanely, the std::string and maybe other datatypes' swap member function if they exist (used via x.swap(y)) simply swaps private pointers and length values if they exist. So swapping two million-character strings takes the same amount of time as swapping two zero-character strings.

As for xor producing overflow: I do not see how xor produces overflow problems. Which is what my question was about (it wasn't about sorting): Does xor have problems when a negative number is involved that causes x ^= y; y ^= x; x ^= y; to not swap the values of x and y when x and y are not the same variable? That is, is there a hypothetical case of internal binary number representation and xor operation where a C or C++-compliant compiler would produce machine code that does not successfully swap, given certain strange values of equally-typed x and y?

[Ancient Dragon]

As for xor producing overflow: I do not see how xor produces overflow problems. Which is what my question was about (it wasn't about sorting): Does xor have problems when a negative number is involved that causes x ^= y; y ^= x; x ^= y; to not swap the values of x and y when x and y are not the same variable? That is, is there a hypothetical case of internal binary number representation and xor operation where a C or C++-compliant compiler would produce machine code that does not successfully swap, given certain strange values of equally-typed x and y?

The xor operator is commonly used in assembly language to set a register value to 0 -- xor if faster at that then moving 0 to the register.

xor does not have a problem with negative values of x or y because it treats x and y as unsigned integers.

Here is an example of the problem with using xor -- the result is 0 for all values of x.

#include <iostream>
using namespace std;

void swap(int& x, int& y)
{
	x ^= y; 
	cout << x << " " << y << endl;
	y ^= x; 
	cout << x << " " << y << endl;
	x ^= y;
	cout << x << " " << y << endl;

}
int main(int argc, char* argv[])
{
	int x = 2;
	swap(x,x);
	return 0;
}

This is the output

0 0
0 0
0 0
Press any key to continue

[Narue]

>Does xor have problems when a negative number is involved
Think about how the bit operations work. Does it make sense for the signed representation to affect those operations in any way?

>I do not see how xor produces overflow problems.
Once again, think about how the bit operations work. Is it possible to overflow a type by only toggling the bits in its value?

is there a hypothetical case of internal binary number representation and xor operation where a C or C++-compliant compiler would produce machine code that does not successfully swap, given certain strange values of equally-typed x and y?

Aside from the points already mentioned, no. Though there are issues where the architecture simply cannot handle an XOR swap without using temporary space, and the compiler would have to pick up the slack. Though those are implementation issues that really have no bearing here except as an argument against the XOR trick because it may not actually save space.

[Rashakil Fol]

Think about how the bit operations work.

Thanks.
I know how bit operations work, but I didn't want to let common sense get in the way of correctly divining the way of the C(++) standards.

[Narue]

>but I didn't want to let common sense get in the way of correctly divining the way of the C(++) standards.
Wise of you.

[kermit]

Because it's useless trivia. Questions like this are basically like tricky riddles: unless you already know it, you probably won't figure it out on your own. You also won't use it in the real world. Even the smallest embedded system will have enough spare memory for a temporary variable, and if it doesn't then there are far better ways to optimize space than to restrict the flexibility of your swap. It's also dreadfully easy to "improve" the trick and break everything, as vegaseat proved. Yes, it's good to know the trick, but it's even better to know why it shouldn't be used.

>the creative kind that get inspired by your puzzles, and the "go by the book apparatchiks"
There's a time and a place for creativity. Code should be written with clarity in mind, and ancient tricks that only serve to create bugs and obfuscate things have no place there. Be creative in your algorithms and you'll be a much better programmer for it. Be creative in "cool" micro-optimization code tricks and you'll just be shrugged off as an idiot who has never worked in the real world.

I would agree with you Narue. What I want to know is what is so 'clever' about these xor tricks? I mean, how many times has everybody seen it? Sure, if you are new to programming forums you might not have, but for those who have spent any time on them, there is a good chance they have seen it more than once. Its old hat - not clever. Its funny how people who are proponents of such code get so offended when someone else points out that perhaps it is not so 'clever' or useful as they would imagine. Why get bent out of shape? I would imagine that nobody in this thread originally thought of the xor trick, so why should one act as if they have a stake in it?

~/

[Narue]

>What I want to know is what is so 'clever' about these xor tricks?
New programmers invariably stumble across them and say "Hey, that's nifty! I think I'll tell everyone I can find so that I look smarter."

>Its old hat - not clever.
For us perhaps, but not for them.

[vegaseat]

>What I want to know is what is so 'clever' about these xor tricks?
New programmers invariably stumble across them and say "Hey, that's nifty! I think I'll tell everyone I can find so that I look smarter."

>Its old hat - not clever.
For us perhaps, but not for them.

This thread started with a simple question:
How can one swap two numbers without a temporary variable?
One solution was the venerable xor way. Nobody advocated cleverness, speed, exclusivity, novelty or reliability of the code. So please folks, let's not be so bumptious about it! Listen/read first, then open your mouth/keyboard and act oh so uppity!

[Narue]

>This thread started with a simple question:
And what makes you think I was referring to this thread? My experiences extend considerably further than the tiny little world of Daniweb, and I feel that it's beneficial if I bring them to bear where they apply.

>One solution was the venerable xor way.
Venerable my ass. Do you even know what that word means? If so, don't you think it's terribly inappropriate for such a despised hack?

>let's not be so bumptious about it!
But we can be "bumptious" about forcing our views that everyone should be nice to each other while actively insulting someone else? Since you're trying to use big, educated words, I have another one for you: hypocrite.

Please don't post again until you have a clue.

[sara.rythm]

Cut it guys!! :confused: , I got my answer. And thanks a lot !! ALL OF YOU have helped a lot !

[Dave Sinkula]

Sounds good to me. Thread closed.