位運算的秒用--異或運算
先來看一個case
咱們今天閒話不用多說,先來看一個小例子。
如何交換兩個數?
問題當然很簡單,交換兩個數,常規的做法是引入一箇中間變數,程式碼如下
func Swap(a, b int){ temp := a //把a的值賦值給臨時變數temp,temp為a的值 a = b //把b的值賦值給a,現在a的值已經變成了b的值 b = temp // 再把之前temp中儲存的a賦值給b即可 }
相信上面的程式碼大家應該都沒問題,但是咱們來加大問題難度,如果不讓引入第三個變數temp,能實現兩個數字的交換麼?
「建議大家先思考兩分鐘再往下看」。
其實很簡單,程式碼如下:
func Swap(a, b int) { a = a ^ b b = a ^ b a = a ^ b }
相信您現在應該和我第一次看到這個程式碼的感覺一樣,這特麼是啥?????這樣能把a和b的值交換?
先不要著急,咱們來一點一點的分析。
異或運算
想要看懂上面的程式碼,首先你得知道什麼叫異或運算。
先看定義
如果a、b兩個值不相同,則異或結果為1。如果a、b兩個值相同,異或結果為0。(這特麼是啥?)沒明白沒有關係,咱們接下來看例子:
舉個例子
比如a=5,b=3。
- 首先 你得把a和b轉換成二進位制,那麼a=101, b= 011。
- 然後a和b進行異或運算,一位一位的去對比,如果值相同,則對應位置異或運算的結果為0,如果值不同,則對應位置異或運算的結果為1。
異或運算示意圖
- 所以a和b的異或運算的結果為 110 也就是6。
- 異或運算也可以按照另外一個角度去理解,就是「無進位的加法」,其實也就是二進位制的相加,但是加完的結果不進位而已。
異或運算的特點
0和任何數N進行異或運算,結果為N
其實這個很好理解,任何數轉換成二進位制,每一位上的數字要麼是0,要麼是1,而和0進行異或,以前是0的位置和0相同,則結果為0,以前是1的位置和0不同,則結果為1,所以運算之後結果是沒變的,如下圖:
任何數和0進行異或運算
任何數N和自己進行異或運算,結果為0
這個也很好理解,N^N每一位肯定都會是一樣的,根據異或運算的法則,結果肯定每一位都為0。
任何數和自己進行異或運算
異或運算滿足交換律和結合律
這個很好理解 也就是說 a^b^c運算 和c^b^a是一樣的。
再來看開頭的例子
當你對異或運算有一定的瞭解了之後,咱們再來看一看開頭的例子:
func Swap(a, b int) { a = a ^ b b = a ^ b a = a ^ b }
第一步運算:
a = a ^ b
第二步運算:
b = a ^ b 因為第一步a=a^b所以在第二步中直接把a替換成a^b即可
所以:
b = a ^ b ^ b
咱們在之前說過,「任何數字對自己進行異或運算的結果都為0」,所以b^b的結果就為0,上面也就等價於。
b= a^0
咱們在上面還說過,「任何數和0進行異或運算,都等於他自己」,所以:
b=a^0 = a
第三步運算:
a = a ^ b
此時b已經運算出來為a,a = a ^ b(第一步運算賦值) 所以第三步運算等價於。
a = a^b^a = 0^b = b(運算細節同第二步)
這樣咱們就可以不用第三個變數進行兩個變數的交換了。
「其他文章」
- 一篇學會樹的子結構
- 從20s優化到500ms,我用了這三招
- 使用 rustup 管理你的 Rust 工具鏈
- Java反序列化基礎篇-JDK動態代理
- iOS 16 即將讓你的 iPhone 擺脫那些特別讓人煩的驗證碼和垃圾廣告
- 刷演算法題常用的 JS 基礎掃盲
- 跨區域、Kubernetes叢集執行資料庫實踐指南
- 13個你應該知道的 Webpack 優化技巧
- Python進行資料視覺化,你會用什麼庫來做呢?
- Python常見報錯及解決方案,建議收藏!
- 介紹一款進階版的 Pandas 資料分析神器:Polars
- Python包管理工具之Pipenv
- 「Spring」Boot Docker 認證指南(上)
- 基於Electron開發Hosts切換工具的“踩坑”之旅
- 2022 年需求中優秀的 DevOps 工具
- 一日一技:如何實現帶Timeout的Input?
- 13 個非常有用的 Python 程式碼片段,建議收藏!
- [科普文] 淺談 Function Programing 程式設計正規化
- 什麼是Pulsar函式流處理應用?
- Flask vs Django: 該如何選擇Python框架?