2009年12月26日

[邏輯運算] 利用互斥進行兩數互換

今天坎尼去上課老師講了一題很有趣的題目
所以回到家坎尼就順手試驗了一下

I. XOR (exclusive OR)

XOR 是邏輯運算子之一,定義為:當兩數的值不同才為 true,相同則為 false
其他相關說明可以參考 維基百科:XOR

II. 程式

以往的做法會宣告一個 temp 變數來當互換的暫存
如果利用 XOR 寫法就變的非常簡單,只要三行就完成互換的動作
( ^ 為C#語法中的 XOR 運算子)
a = a ^ b;
b = a ^ b;
a = a ^ b;

程式執行結果

為什麼會這樣呢? 看了下面的數學推導公式就一目瞭然啦


主要是用到以下幾個特性:
  1. XOR 可交換
  2. 任何數 XOR 本身會得到 0
  3. 任何數 XOR 0 會得到本身
偷偷補充一個:任何數 XOR 1 會得到本身的補數

III. 小結

數學又令原本千篇一律的寫法開創了另一條路呢 ^^

參考網頁:
^ 運算子 (C# 參考)
維基百科:XOR

8 則留言:

Unknown 提到...

補充一下,最近在看 Perl, 其中的【串列】也可以直接進行兩數互換,不需要中間變數,不過不知道內部是怎樣實作的:p http://news.ols3.net/techdoc/old/perl_intro/x420.html : 串列可用來快速交換變數內容,不需要中間暫存變數:

坎尼 提到...

說不定就是內部把 swap 的 code 寫好 XD
swap 這東西在資構上很常應用,應該語言都有內建方法
(只是坎尼才疏學淺不曉得 XD

Unknown 提到...

http://www.google.com.tw/search?rlz=1C1GGLS_zh-TWTW352TW353&sourceid=chrome&ie=UTF-8&q=XOR+%E5%85%A9%E6%95%B8%E4%BA%A4%E6%8F%9B, 第一名ㄟ!可惡我原本也想寫這個題目的 ...

Unknown 提到...

順便補充 Perl 用串列做兩數交換的語法:

($a, $b) = ($b, $a);

超級簡潔XD

坎尼 提到...

大概是這個東西太古老沒人研究
所以才那麼容易衝 Page Rank 吧 XD

那你可以寫一篇 Perl 的... (不過互斥是邏輯上的規則,其實用什麼寫應該都是一樣?)

Unknown 提到...

今天發現 Perl 的串列還有更強大的用法:

($a, $b, $c, $d) = ($b, $a, $d, $c);

這樣就完成 ab 兩變數的值交換、cd 兩變數的值交換,真是輕鬆阿 XD

坎尼 提到...

python 也有類似 perl 的語法

兩數互換
a,b = b,a

n數互換
a,b,c,d = d,c,b,a

Unknown 提到...

這樣作真的是挺直覺的阿,也節省時間,不錯不錯~

Google Spreadsheet 裡用規則運算式

最近因為工作關係,遇到要用 Google Form 及 Google Sheet 所以研究了 Google Sheet 裡的一些 function 怎麼用 首先,分享一下如何在 Google Sheet 裡用規則運算 :D