【Day 5】XOR基礎筆記 |
您所在的位置：网站首页 › 若a⊕b=a⊕c › 【Day 5】XOR基礎筆記 |
【Day 5】XOR基礎筆記
|
前言
這次會先來介紹XOR跟一些它的特性，之後再來解題! XOR 經典文氏圖!
只是覺得南瓜很可愛就想放一下XD 為位元運算(把數字換二進位再去做xor) 位元運算子 : “ ^ “，數學符號 : ⊕，e.g. a^b 、 a⊕b 在條件A 及 B 2項都成立或2項都不成立時 = > 回傳False 在條件A 及 B 中有一項成立及另一項不成立 = > 回傳True 得出真值表
特性
由以上可知 當A = B，A⊕B都會為0，所以得出 A⊕B = 0、A⊕A = 0 => 相同數字去做XOR會互相抵消為0 如B = 0且A != 0， 那麼A⊕B = A，所以得出 A⊕0 = A => 任何數字⊕0結果都會為那個數字 如A = 1、B = 0，A⊕B跟B⊕A的結果相同(都為1)，所以得出 A⊕B = B⊕A => XOR符合交換律有交換律，感覺少了一點什麼，沒錯!XOR也符合結合律喔!不過要稍微想一下，我們回到真值表(懶得往上滑，所以我再放一次圖( •̀ ω •́ )✧) 根據result可知，如果A + B為偶數(0、2)那麼結果為0，反之，如果為奇數(1)那麼結果就為1所以我們可以設一個函式Odd()，如A+B為奇數，那麼Odd(A+B)就會回傳奇數(1)，反之為偶數的話回傳偶數(0)，代表我們可以把A⊕B寫成 A⊕B = Odd(A+B)有了這個，我們來開始證明結合律! 目標 : 證明 A⊕(B⊕C) = (A⊕B)⊕CA⊕(B⊕C)=A⊕(Odd(B+C))=Odd(A+(Odd(B+C)) Odd(A+(Odd(B+C))意思是先把B跟C相加之後判斷奇偶，如相加為奇回傳奇(1)，相加偶回傳偶(0)，之後再加A去判斷奇偶。所以裡面Odd(B+C)也可以寫成B+C(因為B+C跟Odd(B+C)結果的奇偶性會是一樣的，比如說B+C是偶數，代表Odd(B+C)會回傳偶，所以兩者結果都是偶數)，由此可得Odd(A+B+C) =Odd(A+B+C)=Odd(Odd(A+B)+C)=(A⊕B)⊕C 由以上可得知，A⊕(B⊕C) = (A⊕B)⊕C XOR符合結合律https://math.stackexchange.com/questions/293793/prove-xor-is-commutative-and-associative 想要更詳細、或著其他方式證明結合律的話可以看這個網址，主要是我被這個證明方式說服了，加上自己對於這種AND OR運算還不是很熟悉，所以就只介紹這個證明方式 特性小整理符合以下 A⊕0 = A(恆等律) A⊕A = 0(自我抵銷、歸零律) A⊕B = B⊕A(交換律) A⊕(B⊕C) = (A⊕B)⊕C(結合律) A⊕B⊕B = A⊕0 = A(自反) 實作XOR懂了XOR的特性以及觀念，我們先自己手算xor一次，之後再用code來驗證、實作一次吧! 先來隨便設兩個變數，A = 97、B = 15 目標 : 輸出A XOR B的結果 流程 : 先把A跟B轉為2進位，之後一個一個bit做xor，最後把結果轉回10進位得出答案 先來把兩數轉二進位使用短除法，得到餘數之後由下到上就是該數的二進位! 得 A = 1100001、B=1111，接下來做XOR 之後要一個一個做XOR的時候會發現一個大問題，那就是兩個長度不同!解決方法為在比較短的左側去補零，我們上圖!紅色的0就是補0的部分 而為甚麼在左側補0不會影響結果，我們放到最後再來!可以想想看XD 接下來要把結果換成10進位。如XOR result為1，就把它對應的2的次方取出來，結果為 110 所以使用時要記得from pwn import * Code from pwn import * num1 = 97 num2 = 15 print("use ^ :", num1^num2) print("use xor :", ord(xor(num1,num2))) Output
可知兩種方式結果都是一樣的(不過使用xor()他出來會直接轉成字符，所以我偷偷用了ord()把它變回數字)，與我們手算的結果也相同!皆大歡喜R (°▽°)╯ 小結終於結束惹，OMG，位元運算的部分，對於我來說，理解有一點小小吃力，尤其是證明的時候(┬┬﹏┬┬)不過最後弄懂，也學到了好多咚咚不過還沒完!還記得在實作XOR問的問題嗎，我們再來理解一下吧XD 為甚麼在左側補0不會影響結果 可以參考這張圖 由此可知，當二進位值為0的話，不管位於哪，乘出來的結果都會是0，所以可推得int(101010,2) = int(00101010,2)一樣用圖表顯示
下面為在左側加兩個0，但會發現，因為是乘0的關係，所以最後加起來的值是一樣的。 推得，左側加0並不會影響最後結果!理解完畢!今天大概就到這裡惹，休息!明天開始正式解題~ 參考資料XOR維基百科: https://zh.wikipedia.org/zh-tw/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96 XOR文式圖 : https://www.cool3c.com/article/157771 XOR位元運算子介紹 : https://medium.com/@hyWang/xor-%E4%BD%8D%E5%85%83%E9%81%8B%E7%AE%97%E5%AD%90-1c25b4ae15fb 證明XOR結合律(Prove XOR is commutative and associative) : https://math.stackexchange.com/questions/293793/prove-xor-is-commutative-and-associative 兩數二進位長度不同做XOR : https://stackoverflow.com/questions/31520787/how-to-xor-two-binary-numbers-having-different-length 二進位算法 : https://tomchun.tw/tomchun/2015/11/11/1-91/ 二進位轉十進位 : https://www.geeksforgeeks.org/binary-to-decimal/ |
手算完後，我們用程式碼來進行驗證，有兩種方式，第一個為使用^來做XOR，第二種為使用pwntools函式庫中的xor()
【本文地址】
今日新闻 |
推荐新闻 |