資訊專欄INFORMATION COLUMN
摘要：開心一刻兩頭奶牛在一起吃草，其中一頭奶牛甲越吃越慢，一副若有所思的模樣，另一頭奶牛奶牛乙發(fā)覺了，開始了對話奶牛乙擱那合計啥呢奶牛甲你幫我合計合計奶牛乙咋地了奶牛甲我吃的是草，擠出來的是奶，也就是說我把沒用的變成有用的了奶牛乙是這個事奶牛甲人
兩頭奶牛在一起吃草，其中一頭（奶牛甲）越吃越慢，一副若有所思的模樣，另一頭奶牛（奶牛乙）發(fā)覺了，開始了對話
奶牛乙：擱那合計啥呢？
奶牛甲：你幫我合計合計
奶牛乙：咋地了
奶牛甲：我吃的是草，擠出來的是奶，也就是說我把沒用的變成有用的了
奶牛乙：是這個事
奶牛甲：人呢，喝的是奶，拉出來的是粑粑
奶牛乙：咋地了
奶牛甲：他又把有用的變成沒用的了，我這不白干了嗎
奶牛乙：你說的不對
奶牛甲：不對嗎？
奶牛乙：那粑粑做成化肥，有化肥才能長草，所以說你吃的不是草，是粑粑
奶牛乙：啊 ？？？
關(guān)于“位”運算，大家或多或少都知道點，比如與運算（&）、或運算（|）、異或運算（^）、取反運算（~）、左移（<<）、右移（>>）
因為今天的主角是：異或運算，其他的位運算就不在本文展開了，大家自行去查閱
異或運算的英文名：?exclusive OR?，簡稱?XOR?，那它是不是和或運算有什么關(guān)系？
關(guān)于或運算，我們都比較清楚，只有當(dāng)兩個位都是0時，結(jié)果才為0，其他情況結(jié)果都是1，也就是說或運算結(jié)果為?1?的情況兩種
（1）一個位是 1，另一個位是 0
（2）兩個位都是 1
有時候我們需要明確區(qū)分這兩種情況，怎么辦？
所以引入了?XOR?，它排除了情況（2），只有情況（1），也就說：一個位是 1，另一個位是 0 時，?XOR?的結(jié)果才是 1，因此也可稱做無進位相加
所以 ?XOR?可以看成是更單純的 OR 運算，正好對應(yīng)了它的英文名：?exclusive OR?，用來判斷兩個值是否不同（不同、不同、不同！！！）
?XOR?的運算真值表
我們學(xué)過的加法、乘法都有運算定律，異或運算也有它的運算定律
N 表示任何值，也就是說：兩個相等的值做異或運算，得到的結(jié)果是 0
因為值相等，那么值對應(yīng)的各個位的值也是相等的，對應(yīng)到?XOR?的運算真值表則是
我們來看個具體的例子：15 ^ 15
15 對應(yīng)的二進制位：?01111?，那么 15 ^ 15 的運算則是
一個值與 0 做異或運算，得到的結(jié)果仍是這個值
例如：15 ^ 0 = 15
同加法有交換律、乘法也有交換律一樣，異或運算也有交換律
例如：15 ^ 8 = 8 ^ 15
同加法有結(jié)合律、乘法有結(jié)合律一樣，異或運算也結(jié)合律
例如：(15 ^ 8) ^ 3 = 15 ^ (8 ^ 3)
前面講了那么多理論，大家可能沒啥感覺，接下來我們就看看具體的案例，讓大家好好感覺感覺
樓主在以往的面試過程中，確確實實被面到過這個問題，關(guān)鍵是當(dāng)時沒答上來
這個問題的考點就是?XOR?
假設(shè)這兩個變量分別是 N（值為 5）、M（值為 6），通過三次?XOR?即可交換 N、M 的值
N = N ^ M // N = 5 ^ 6， M = 6
M = N ^ M // M = 5 ^ 6 ^ 6 = 5 ^ 0 = 5，N = 5 ^ 6
N = N ^ M // N = 5 ^ 6 ^ 5 = 6 ^ 0 = 6，M = 5
問題詳細描述：已知一串?dāng)?shù)中，只有 1 個數(shù)字出現(xiàn)了奇數(shù)次，其他數(shù)字都出現(xiàn)了偶數(shù)次，如何快速找到這個奇數(shù)次的數(shù)字
如果沒有任何限制，解決方式有很多種，而最容易想到的往往是用?哈希表?
對這串?dāng)?shù)字從頭遍歷到尾，?逐個判斷該數(shù)字是否存在于哈希表?，沒有存在則存入?哈希表?，存在了則從?哈希表?中移除
最終?哈希表?中剩下的那個數(shù)字就是出現(xiàn)了奇數(shù)次的數(shù)字
?哈希表?方案的時間復(fù)雜度是?O(N)?，額外空間復(fù)雜度也是?O(N)?
假設(shè)加個限制：額外空間復(fù)雜度?O(1)?
這時候就該?XOR?出馬了，我們結(jié)合?N ^ N = 0?、異或的交換律、異或的結(jié)合律，可推算出：這串?dāng)?shù)字全部進行異或運算，最終的結(jié)果就是出現(xiàn)了奇數(shù)次的那個數(shù)字
?
? 此時的額外空間復(fù)雜度是?O(1)?，只用到了兩個額外變量：?eor?、?cur?
問題詳細描述：一串?dāng)?shù)字包含 n-1 個成員，這些數(shù)字是 1 到 n 之間的整數(shù)，且沒有重復(fù)，請找出缺少的那個數(shù)字
常規(guī)解法：從 1 累和到 n，然后再逐個減去這串?dāng)?shù)字
類似這樣?1 + 2 + ... + n - arr[0] - arr[1] - ... - arr[n-2]?
時間復(fù)雜度?O(N)?，空間復(fù)雜度?O(1)?，似乎很完美
但是求和的過程存在溢出的風(fēng)險，那怎么辦？?XOR?閃亮登場
我們將這串?dāng)?shù)組與 1 至 n 的每個整數(shù)放在一起進行全部的異或運算
類似這樣?arr[0] ^ arr[1] ^ ... ^ arr[n-2] ^ 1 ^ 2 ^ ... ^ n?
那么得到的結(jié)果就是缺少的那個數(shù)
不存在溢出的風(fēng)險，并且位運算比加、減運算更快
問題詳細描述：一串?dāng)?shù)字包含 n+1 個成員，這些數(shù)字是 1 到 n 之間的整數(shù)，只有一個數(shù)字出現(xiàn)了兩次，其他數(shù)字都只出現(xiàn)一次，請找出重復(fù)出現(xiàn)的那個數(shù)字
與問題：找出 1 至 n 中缺少的那個數(shù)解法一致
?arr[0] ^ arr[1] ^ ... ^ arr[n] ^ 1 ^ 2 ^ ... ^ n?
問題詳細描述：已知一串?dāng)?shù)中，有 2 個數(shù)字出現(xiàn)了奇數(shù)次，其他數(shù)字都出現(xiàn)了偶數(shù)次，如何快速找到那 2 個奇數(shù)次的數(shù)字
要求：時間復(fù)雜度?O(N)?，空間復(fù)雜度?O(1)?
經(jīng)過上面幾題的洗禮，我相信大家對?奇數(shù)次?、?偶數(shù)次?字眼已經(jīng)產(chǎn)生了條件反射：用?XOR?
我們對這串?dāng)?shù)字進行?XOR?，那么得到的結(jié)果?eor = a ^ b?，a 和 b 就是那兩個出現(xiàn)了奇數(shù)次的數(shù)字
因為?a != b?，則?eor != 0?，所以?eor?肯定有某一個二進制位是 1
我們?nèi)?eor?二進制最右邊的 1：?int rightOne = eor & (~eor + 1)?
通過?rightOne?可以將數(shù)字串拆成兩部分：cur & rightOne = 0?和?cur & rightOne != 0?
a、b 分別落在兩側(cè)，其他偶數(shù)個的數(shù)字只會落在某一側(cè)，整個數(shù)字串就被拆分成兩個找出一串?dāng)?shù)字中唯一出現(xiàn)了奇數(shù)次的數(shù)字的數(shù)據(jù)模型了
分別從兩側(cè)中找出奇數(shù)次的數(shù)字即可
完整代碼如下
這個解法沒那么好理解，大家好好琢磨琢磨
1、?XOR?用來判斷同位上的值是否不同
2、 出現(xiàn)奇數(shù)個?、?偶數(shù)個?、?缺失的?、?重復(fù)的?字眼，可以往?XOR?考慮
3、關(guān)于 不用額外的變量交換兩個變量的值，大家了解就好，不推薦使用
閱讀性差，另外相比臨時變量，它可能會出問題
4、示例代碼地址
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/125681.html
摘要：并且，一些偽元素可以使開發(fā)者獲取到不存在于源文檔中的內(nèi)容比如常見的還可以為偽元素定制樣式。。中新增加的偽元素必須用偽類使用一個冒號例如。就本文而言，我們將把我們探討的范圍限制在和這兩個偽元素的巧用上。 作為一門前端er,你肯定熟知 a:hover ? ??a:visited.....我還記得在小本本上記著訣竅：love 與 hate 糾纏不休,大家都懂的吧。。。。 ? ?????偽類和...
摘要：選擇排序算法實現(xiàn)實現(xiàn)選擇排序，記錄最小元素的索引，最后才交換位置說明交換兩個數(shù)組中的元素，在中有更簡單的寫法，這是的語法糖，其它語言中是沒有的。和語言中比較器的實現(xiàn)前面我們說到了，我們?yōu)榱送怀雠判蛩惴ǖ乃枷耄瑢⑺械睦觾H限在數(shù)組排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...
摘要：位算法的效率有多快我就不說，不信你可以去用億個數(shù)據(jù)模擬一下，今天給大家講一講位運算的一些經(jīng)典例子。不過，最重要的不是看懂了這些例子就好，而是要在以后多去運用位運算這些技巧，當(dāng)然，采用位運算，也是可以裝逼的，不信，你往下看。位算法的效率有多快我就不說，不信你可以去用 10 億個數(shù)據(jù)模擬一下，今天給大家講一講位運算的一些經(jīng)典例子。不過，最重要的不是看懂了這些例子就好，而是要在以后多去運用位運算這...
閱讀 3735·2023-01-11 11:02
閱讀 4244·2023-01-11 11:02
閱讀 3050·2023-01-11 11:02
閱讀 5180·2023-01-11 11:02
閱讀 4737·2023-01-11 11:02
閱讀 5534·2023-01-11 11:02
閱讀 5313·2023-01-11 11:02
閱讀 3990·2023-01-11 11:02
