JBTALKS.CC

标题: [分享] Variable swapping 的方法 [打印本页]
作者: Dhilip89    时间: 2010-9-13 06:26 AM
标题: [分享] Variable swapping 的方法
本帖最后由 Dhilip89 于 2010-9-13 06:36 AM 编辑

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

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

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

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

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

  16.     return 0;
  17. }
复制代码
输出结果：
var1 = 20, var2 = 75
var1 = 75, var2 = 20

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

现在我介绍不用第三个variable也可以进行数值对换的方法：
  1. #include <stdio.h>

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

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

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

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

  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...)。

小弟我可能会写错东西，望高手指点。
作者: 宅男-兜着走    时间: 2010-9-13 12:19 PM
有一段时间没上来这里了。
相信每个程序员都有写过数值对换的代码吧，但是大部分的人会使用以下的方法来实 ...
Dhilip89 发表于 2010-9-13 06:26 AM


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

第二种方法， 浮点用不到就xian 了。
那么你说第二种方法比对第一种方法有什么好处？（除了不必 declare temp）
作者: Super-Tomato    时间: 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    时间: 2010-9-19 11:43 AM
以上的只是纯粹分享，这方法虽然性能不佳，但是可以让其他还没接触过的人认识一下。



欢迎光临 JBTALKS.CC (https://www.jbtalks.my/) Powered by Discuz! X2.5