查看: 959|回复: 3

[分享] Variable swapping 的方法

3 主题	0 好友	2953 积分

白金长老

Rank: 10

发消息

电梯直达

1^#

发表于 2010-9-13 06:26 AM |只看该作者 |倒序浏览

本帖最后由 Dhilip89 于 2010-9-13 06:36 AM 编辑

有一段时间没上来这里了。
相信每个程序员都有写过数值对换的代码吧，但是大部分的人会使用以下的方法来实现数值对换：

#include <stdio.h>
int main(void)
{
int var1 = 20, var2 = 75, temp;
printf("var1 = %d, var2 = %d\n", var1, var2);
// swap the variable
temp = var1;
var1 = var2;
var2 = temp;
printf("var1 = %d, var2 = %d\n", var1, var2);
return 0;
}

复制代码

输出结果：

var1 = 20, var2 = 75
var1 = 75, var2 = 20

以上的方法会使用到第三个variable来进行对换。

现在我介绍不用第三个variable也可以进行数值对换的方法：

#include <stdio.h>
int main(void)
{
int var1 = 20, var2 = 75;
printf("var1 = %d, var2 = %d\n", var1, var2);
// swap the variable
var1 ^= var2; //same as: var1 = var1 ^ var2
var2 ^= var1;
var1 ^= var2;
printf("var1 = %d, var2 = %d\n", var1, var2);
return 0;
}

复制代码

输出结果：

var1 = 20, var2 = 75
var1 = 75, var2 = 20

以上的方法是使用了XOR(bitwise operation)来达到数值对换的效果。

对于不熟悉bitwise operation的人应该会问：它是如何运作呢？
其实原理很简单：

以上采用了XOR，也就是eXclusive OR
OR 和 XOR 的差别：

1 OR 0 = 1
0 OR 0 = 0
1 OR 1 = 1

1 XOR 0 = 1
0 XOR 0 = 0
1 XOR 1 = 0

以下就是它的运作原理：

Swaping two variables with XOR swapping algorithm:

Original:

   a = 10010010
   b = 11101011

      Step 1:

         a = a ^ b

            10010010  <-- a
            ^ 11101011  <-- b
            ----------
            01111001  <-- a
            ----------

      Step 2:

         b = b ^ a

            11101011  <-- b
            ^ 01111001  <-- a
            ----------
            10010010  <-- b
            ----------

      Step 3:

         a = a ^ b

            01111001  <-- a
            ^ 10010010  <-- b
            ----------
            11101011  <-- a
            ----------

Swapped:

      a = 11101011
      b = 10010010

注意：
以上方法不能用在浮点数值(float, double)。
进行对换的两者都必需同类型(int ^ int, char ^ char, short ^ short, etc...)。

小弟我可能会写错东西，望高手指点。

swapping , XOR , 数值对换

收藏0

使用道具举报

宅男-兜着走

46 主题	6 好友	6456 积分

百变名嘴

Rank: 13

发消息

2^#

发表于 2010-9-13 12:19 PM |只看该作者

有一段时间没上来这里了。
相信每个程序员都有写过数值对换的代码吧，但是大部分的人会使用以下的方法来实 ...
Dhilip89 发表于 2010-9-13 06:26 AM

第一种方法，比较Common，支持多数 Data types（还是是所有）

,

第二种方法，浮点用不到就xian 了。
那么你说第二种方法比对第一种方法有什么好处？（除了不必 declare temp）

使用道具举报

Super-Tomato

7 主题	1 好友	5108 积分

一流名嘴

Rank: 12

发消息

3^#

发表于 2010-9-13 02:28 PM |只看该作者

有一段时间没上来这里了。
相信每个程序员都有写过数值对换的代码吧，但是大部分的人会使用以下的方法来实现数值对换：

1. #include <stdio.h>
2.

3. int main(void)
4. {
5.    int var1 = 20, var2 = 75, temp;
6.

7.    printf("var1 = %d, var2 = %d\n", var1, var2);
8.

9.    // swap the variable
  10.    temp = var1;
  11.    var1 = var2;
  12.    var2 = temp;
  13.

  14.    printf("var1 = %d, var2 = %d\n", var1, var2);
  15.

  16.    return 0;
  17. }

复制代码
输出结果：

var1 = 20, var2 = 75
var1 = 75, var2 = 20

以上的方法会使用到第三个variable来进行对换。

现在我介绍不用第三个variable也可以进行数值对换的方法：

1. #include <stdio.h>
2.

3. int main(void)
4. {
5.    int var1 = 20, var2 = 75;
6.

7.    printf("var1 = %d, var2 = %d\n", var1, var2);
8.

9.    // swap the variable
  10.    var1 ^= var2; //same as: var1 = var1 ^ var2
  11.    var2 ^= var1;
  12.    var1 ^= var2;
  13.

  14.    printf("var1 = %d, var2 = %d\n", var1, var2);
  15.

  16.    return 0;
  17. }

复制代码
输出结果：

var1 = 20, var2 = 75
var1 = 75, var2 = 20

以上的方法是使用了XOR(bitwise operation)来达到数值对换的效果。

对于不熟悉bitwise operation的人应该会问：它是如何运作呢？
其实原理很简单：

以上采用了XOR，也就是eXclusive OR
OR 和 XOR 的差别：

1 OR 0 = 1
0 OR 0 = 0
1 OR 1 = 1

1 XOR 0 = 1
0 XOR 0 = 0
1 XOR 1 = 0

以下就是它的运作原理：

Swaping two variables with XOR swapping algorithm:

      Original:

         a = 10010010
         b = 11101011

         Step 1:

            a = a ^ b

                  10010010  <-- a
               ^ 11101011  <-- b
               ----------
                  01111001  <-- a
               ----------

         Step 2:

            b = b ^ a

                  11101011  <-- b
               ^ 01111001  <-- a
               ----------
                  10010010  <-- b
               ----------

         Step 3:

            a = a ^ b

                  01111001  <-- a
               ^ 10010010  <-- b
               ----------
                  11101011  <-- a
               ----------

      Swapped:

         a = 11101011
         b = 10010010

注意：
以上方法不能用在浮点数值(float, double)。
进行对换的两者都必需同类型(int ^ int, char ^ char, short ^ short, etc...)。

小弟我可能会写错东西，望高手指点。
Dhilip89 发表于 2010-9-13 06:26 AM

XOR 确实也是個方式，但以前測試過执行速度方面比用 temp 的方式较慢，而最快的是使用偏移的方式，但并不是所有語言适用

使用道具举报

Dhilip89

3 主题	0 好友	2953 积分

白金长老

Rank: 10

发消息

4^#

发表于 2010-9-19 11:43 AM |只看该作者

以上的只是纯粹分享，这方法虽然性能不佳，但是可以让其他还没接触过的人认识一下。

使用道具举报

返回列表