so true

          心懷未來,開創未來!
          隨筆 - 160, 文章 - 0, 評論 - 40, 引用 - 0
          數據加載中……

          [轉載]不用臨時變量也可以交換變量的值

          當要交換兩個數的值時,通常的做法是定義一個臨時變量,然后再進行交換。那么能不能不用臨時變量而交換兩個數的值呢?可以的!C語言提供的異或運算就可以實現這樣的操作。 
          異或運算符^也稱XOR運算符,它的規則是若參加運算的兩個二進位同號,則結果為0(假);異號為1(真)。即0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0。 
          例:

          #include <stdio.h>

          int main(int argc, char *argv[])
          {
              int a = 2, b = 6;

              a = a ^ b;
              b = b ^ a;
              a = a ^ b;

              printf("a = %d b = %d\n", a, b);

              return 0;
          }

          結果如下:

          a = 6 b = 2

          分析:

          前兩個賦值語句:“a = a ^ b;”和“b = b ^ a;”相當于b = b ^ (a ^ b),而b ^ a ^ b等于a ^ b ^ b。b ^ b的結果為0,因為同一個數與相向相^,結果必為0。因此b的值等于a ^ 0,即a,其值為2。

          再執行第三個賦值語句:“a = a ^ b”。由于a的值等于(a ^ b),b的值等于(b ^ a ^ b),因此,相當于a = a ^ b ^ b ^ a ^ b,即a的值等于a ^ a ^ b ^ b ^ b,等于b。

          今天又發現另外兩種方法,特補上。 
          方法一

          void swap(int *p, int *q)
          {
              *p = *p + *q;
              *q = *p - *q;
              *p = *p - *q;
          }

          方法二

          void swap(int *p, int *q)
          {
              *p = *p + *q - (*q = *p);
          }

          原理為算術運算符的結合順序為自左至右。

          2007.06.18
           
          可以把異或的三條語句壓縮為一條: 

          a ^= b ^= a ^= b;

          要交換三個變量的值,可以用以下語句:

          c = a + c - (a = b, b = c);

          2007.09.11

          謝謝網友cool8jay指出上面紅色部分的錯誤,下面來分析一下,先看一個示例程序,如下:

          #include <stdio.h>

          int main(int argc, char *argv[])
          {
              int a = 1;
              int b = 2;
              int c = 3;

              c = a + c - (a = b, b = c);

              printf("a = %d\n", a);
              printf("b = %d\n", b);
              printf("c = %d\n", c);

              return 0;
          }

          編譯運行,結果如下:

          a = 2 b = 3 c = 2

          可見,最初目標中的c = 1部分沒能實現。于是分析原因:

          《The C Programming Language·Second Edition》P205介紹說,“The additive operators + and - group left-to-right”,即附加運算符加號和減號的結合順序是自左向右;P209介紹說,“A pair of expressions separated by a comma is evaluated left-to-right, and the value of the left expression is discarded. The type and value of the result are the type and value of the right operand”,即逗號表達式的計算順序是從左向右,逗號左邊表達式的值被舍棄,表達式結果的類型和數值是逗號右邊表達式的類型和數值。

          既然如此,那結果應該是正確的,為什么還會出錯呢?再來看一下VC6.0下編譯產生的匯編代碼:

          7: int a = 1;
          00401028 mov dword ptr [ebp-4],1
          8: int b = 2;
          0040102F mov dword ptr [ebp-8],2
          9: int c = 3;
          00401036 mov dword ptr [ebp-0Ch],3
          10:
          11: c = a + c - (a = b, b = c);
          0040103D mov eax,dword ptr [ebp-8]
          00401040 mov dword ptr [ebp-4],eax
          00401043 mov ecx,dword ptr [ebp-4]
          00401046 add ecx,dword ptr [ebp-0Ch]
          00401049 mov edx,dword ptr [ebp-0Ch]
          0040104C mov dword ptr [ebp-8],edx
          0040104F sub ecx,dword ptr [ebp-8]
          00401052 mov dword ptr [ebp-0Ch],ecx

          可以看到,第11行代碼的執行過程如下:

          先把b的值賦給a,再把a和c的值相加,結果放在寄存器ecx中,然后把c的值賦給b,最后再把ecx與b的值相減,結果賦給c。分解為C語句為:

          a = b; /* a = 2, b = 2 */
          ecx = a + c; /* ecx = 5, a = 2, c = 3 */
          b = c; /* b = 3, c = 3 */
          c = ecx - b; /* c = 2, ecx = 5, b = 3 */

          這下就清楚了,原來程序運行時先把逗號左邊表達式的值計算出來丟棄掉,然后再做其它的運算,最開始的錯誤也就錯在了這里。

          好了,既然上面的式子有問題,那有沒有其它正確的方法能一條語句實現三個變量的值的交換呢?恕本人愚鈍,還沒有想出來。如果誰知道,請給我留言。在此先致謝!

          還有一個問題,也是網友cool8jay提出來的,就是交換三個變量的值(每個變量值都要改變)應該有兩種情況,123可以變為231或312。我當時想到過,只是覺得可以類比就沒有說明,現在看來可能會誤導讀者,這里說明一下。

          不用臨時變量順次交換N個變量的值
          有N(N>=2)個變量,不使用臨時變量,如何順次交換它們的值?能否只用一條語句實現?如
           
          +---+---+---+---+---+
          | a | b | c | d | e |
          +---+---+---+---+---+
          | 1 | 2 | 3 | 4 | 5 |
          +---+---+---+---+---+
           
          要把它變為
           
          +---+---+---+---+---+
          | a | b | c | d | e |
          +---+---+---+---+---+
          | 2 | 3 | 4 | 5 | 1 |
          +---+---+---+---+---+
           
          怎樣實現?
           
          首先,我們考慮用異或實現兩個變量的交換,可參考我的這篇文章《不用臨時變量交換兩個數的值》。用C++寫函數如下:
           

          int &swap(int &a, int &b)
          {
              b = b ^ a;
              a = a ^ b;
              b = b ^ a;

              return b;
          }

          然后可以把代碼優化為:

          int &swap(int &a, int &b)
          {
              b ^= a;
              a ^= b;
              b ^= a;

              return b;
          }

          繼續優化,把三句壓縮為一句,如下:

          int &swap(int &a, int &b)
          {
              b ^= a ^= b ^= a;
              
              return b;
          }

          還可再優化,如下:

          int &swap(int &a, int &b)
          {
              return (b ^= a ^= b ^= a);
          }

          現在來順次交換5個變量的值,如下:

          swap(a, b);        //返回b

          swap(b, c);        //返回c

          swap(c, d);        //返回d

          swap(d, e);        

          既然有返回值,那么可以寫成鏈式的,如下:

          swap(a, b);                                 //返回b

          swap(swap(a, b), c);                        //返回c

          swap(swap(swap(a, b), c), d);               //返回d

          swap(swap(swap(swap(a, b), c), d), e);        

          現在,讓我們來把swap函數依次用相應的函數體替換掉,如下:

          e ^= d ^= e ^= swap(swap(swap(a, b), c), d);

          e ^= d ^= e ^= d ^= c ^= d ^= swap(swap(a, b), c);

          e ^= d ^= e ^= d ^= c ^= d ^= c ^= b ^= c ^= swap(a, b);

          e ^= d ^= e ^= d ^= c ^= d ^= c ^= b ^= c ^= b ^= a ^= b ^= a;

          好了,最后一個語句就實現了順次交換五個變量的值,寫程序驗證如下:

          /******************************************************************
          * Copyright (c) 2005-2007 CUG-CS
          * All rights reserved
          *
          * 文件名稱:xor.c
          * 簡要描述:實現五個變量的順次交換
          *
          * 當前版本:1.0
          * 作 者:raincatss
          * 完成日期:2007-10-18
          * 開發環境:Windows XP Sp2 + VC6.0
          * 個人博客:http://raincatss.cublog.cn/
          ******************************************************************/


          #include <stdio.h>

          #define PRINT(A) do {\
              printf("%d\n", A);\
              } while (0)

          int main()
          {
              int a = 1;
              int b = 2;
              int c = 3;
              int d = 4;
              int e = 5;

          //    b ^= a ^= b ^= a;        // swap(a, b)

          //    c ^= b ^= c ^= b;        // swap(b, c)

          //    d ^= c ^= d ^= c;        // swap(c, d)

          //    e ^= d ^= e ^= d;        // swap(d, e)


              e ^= d ^= e ^= d ^= c ^= d ^= c ^= b ^= c ^= b ^= a ^= b ^= a;

              PRINT(a);
              PRINT(b);
              PRINT(c);
              PRINT(d);
              PRINT(e);

              return 0;
          }

          運行結果如下:

          2 3 4 5 1

          測試結果正確,達到預定目標。

          posted on 2008-03-10 12:53 so true 閱讀(737) 評論(0)  編輯  收藏 所屬分類: C&C++

          主站蜘蛛池模板: 汶川县| 乐陵市| 昆明市| 建瓯市| 武鸣县| 邓州市| 通州市| 秦安县| 治多县| 枣阳市| 阿合奇县| 长沙县| 马关县| 海原县| 汉寿县| 开远市| 屏南县| 赣州市| 东方市| 文昌市| 江西省| 襄垣县| 长子县| 二手房| 吉木乃县| 白水县| 麻栗坡县| 海口市| 石城县| 和平区| 枝江市| 吉林市| 亚东县| 博兴县| 星座| 文安县| 秭归县| 金昌市| 河津市| 榆树市| 玉环县|