12

I've learned that Xor operation can be used to implement effective swap function. like this:

template<class T>
void swap(T& a, T& b)
{
    a = a^b;
    b = a^b;
    a = a^b;
}

But the implementation of swap all i can found on the internet is essentially like this:

template<class T>
void swap(T& a, T& b)
{
    T temp(a);
    a = b;
    b = temp;
}

It seems that the compiler didn't generate the same code for the two form above because I tested it on VC++ 2010 and the first one is done the job more quickly than std::swap. Is there portable or any other problem with first one? Feel free to correct any of my mistake cause i'm not an English native and not good at C++.

(Editor's note: likely that test was done with a non-optimized debug build, not a release build where std::swap could inline. Benchmarking debug builds is meaningless. Compilers generally don't optimize away xor-swap into something more efficient.)

4

5 回答 5

20

我了解到可以使用异或操作来实现有效的交换功能

你学错了，我怕。XOR 交换已过时：如果它比使用临时值可靠地快，那么它不应该出现在现代编译器和处理器上（“现代”我的意思是大约过去 20 年或更长时间）。你说它对你来说更快，可能你应该展示你的基准代码，看看其他人是否得到相同的结果。

除了您的代码仅适用于整数类型这一事实之外，它还有一个基本错误。用你的交换版本试试这个：

int a = 1;
swap(a,a);
std::cout << a << '\n';
于 2012-05-11T10:17:34.020 回答
11

效果取决于你在哪里使用它。

在普通 cpu 上，两个整数变量的普通交换看起来像

$1 <- a
$2 <- b
a <- $2
b <- $1

4 次操作，2 次加载，2 次存储，最长依赖为 2

以异或方式：

$1 <- a
$2 <- b
$3 <- $1 ^ $2
$4 <- $3 ^ $2
$5 <- $3 ^ $4
a <- $5
b <- $4

7 个操作，2 个加载，2 个存储，3 个逻辑，最长依赖为 4

因此，即使适用，至少通常与 xor 交换也会更慢。

于 2012-05-11T10:05:46.520 回答
4

我认为最明显的原因是 XOR 运算符仅对整数类型有意义。

于 2012-05-11T09:55:09.737 回答
2

当然，因为这个xor技巧适用于 POD 类型。

如果你想交换两个用户定义的复杂类型，xor那是行不通的。你需要一个深拷贝，而不是原始内存的直接拷贝，这有点xor像。

编辑：

我在 VC++ 2010 上对其进行了测试，第一个完成的工作更快（并且比 std::swap 更快）。

真的吗？你是在调试模式下编译的吗？你的结果是什么？

于 2012-05-11T09:54:42.137 回答
0

首先，XOR 运算符只为整数类型定义。

其次，您可以使用强制转换技巧将非整数类型转换为整数形式。

但第三，对于除 POD 类型之外的所有类型，这都会导致未定义的行为，

第四，对于 XOR 操作没有得到很好支持的大小/对齐方式的类型，需要更多的玩弄（循环是最不邪恶的）。

您可以重载operator^, 但这意味着 的每个特化都swap()必须确保它存在或定义一个，这可能会在名称查找时产生更多的混乱，而不是值得的。当然，如果这样的运算符已经存在，它不一定具有正确的行为，并且您可能最终得到更差的性能，因为这种重载不一定是inlineor constexpr。

于 2012-05-11T09:59:31.253 回答