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