自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

你說(shuō)你會(huì)位運(yùn)算，那你用位運(yùn)算來(lái)解下八皇后問(wèn)題吧

作者：碼海
存儲(chǔ)
位運(yùn)算在生產(chǎn)或算法解題中并不常見(jiàn)，不過(guò)如果你用得好，可以達(dá)到事半功倍的效果，而且位運(yùn)算用得好，也可以極大地提升性能。

前言

位運(yùn)算在生產(chǎn)或算法解題中并不常見(jiàn)，不過(guò)如果你用得好，可以達(dá)到事半功倍的效果，而且位運(yùn)算用得好，也可以極大地提升性能，如果在生產(chǎn)或面試中能看到使用位運(yùn)算來(lái)解題，會(huì)讓人眼前一亮，覺(jué)得你還是有點(diǎn)逼格的，巧用位運(yùn)算，不僅會(huì)提升性能，還會(huì)讓代碼的可讀性更好，達(dá)到四兩撥千斤的效果，今天我們就來(lái)學(xué)學(xué)位運(yùn)算在解題中的一些技巧，最后會(huì)用位運(yùn)算來(lái)看看怎么解八皇后這道大 Boss 題，相信你看完肯定會(huì)有收獲!

[[319856]]

本文將會(huì)從以下幾個(gè)方面來(lái)講解位運(yùn)算

  • 什么是位運(yùn)算，位運(yùn)算常見(jiàn)操作
  • 位運(yùn)算使用技巧簡(jiǎn)介
  • 巧用位運(yùn)算解算法題

什么是位運(yùn)算，位運(yùn)算常見(jiàn)操作

在現(xiàn)代計(jì)算機(jī)中所有的數(shù)據(jù)在內(nèi)存中都是以二進(jìn)制存在的，位運(yùn)算就是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作，由于位運(yùn)算直接對(duì)內(nèi)存數(shù)據(jù)進(jìn)行操作，無(wú)需轉(zhuǎn)成十進(jìn)制，因此使用位運(yùn)算的處理速度是很快的。

舉個(gè)簡(jiǎn)單的例子， 當(dāng)我們要計(jì)算 6 & 4 的結(jié)果，在做位運(yùn)算的時(shí)候首先要把 6，4 轉(zhuǎn)成二進(jìn)制，然后再做相應(yīng)的位操作(與)。

基本的位運(yùn)算有與、或、異或、取反、左移、右移這6種，介紹如下：

& 與：只有當(dāng)兩位都是 1 時(shí)結(jié)果才是 1，否則為 0 。

  1.  0110 
  2. &   0100 
  3. ----------- 
  4.     0100 

| 或：兩位中只要有 1 位為 1 結(jié)果就是 1，兩位都為 0 則結(jié)果為 0。

  1.  0110 
  2. &   0110 
  3. ----------- 
  4.     0110 

^ 異或：兩個(gè)位相同則為 0，不同則為 1

  1.   0110 
  2. ^   0100 
  3. ----------- 
  4.     0010 

~ 取反：0 則變?yōu)?1，1 則變?yōu)?0

  1. ~   0110 
  2. ----------- 
  3.     1001 

<< 左移：向左進(jìn)行移位操作，高位丟棄，低位補(bǔ) 0

  1. int a = 8; 
  2. a << 3; 
  3. 移位前：0000 0000 0000 0000 0000 0000 0000 1000 
  4. 移位后：0000 0000 0000 0000 0000 0000 0100 0000 

>> 右移：向右進(jìn)行移位操作，對(duì)無(wú)符號(hào)數(shù)，高位補(bǔ) 0，對(duì)于有符號(hào)數(shù)，高位補(bǔ)符號(hào)位

  1. unsigned int a = 8; 
  2. a >> 3; 
  3. 移位前：0000 0000 0000 0000 0000 0000 0000 1000 
  4. 移位后：0000 0000 0000 0000 0000 0000 0000 0001 
  5.  
  6. int a = -8; 
  7. a >> 3; 
  8. 移位前：1111 1111 1111 1111 1111 1111 1111 1000 
  9. 移位后：1111 1111 1111 1111 1111 1111 1111 1111 

位運(yùn)算使用技巧簡(jiǎn)介

接下來(lái)我們就由淺入深地來(lái)學(xué)習(xí)一下使用位運(yùn)算的那些黑科技

1、 判斷整型的奇偶性

使用位運(yùn)算操作如下

  1. if((x & 1) == 0) { 
  2.     // 偶數(shù) 
  3. } else { 
  4.     // 奇數(shù) 
  5. } 

這個(gè)例子相信大家都見(jiàn)過(guò)，只需判斷整型的第一位是否是 1 即可，如果是說(shuō)明是奇數(shù)，否則是偶數(shù)

2、 判斷第 n 位是否設(shè)置為 1

  1. if (x & (1<<n)) { 
  2.     // 第 n 位設(shè)置為 1 
  3. } 
  4. else { 
  5.     // 第 n 位設(shè)置為 1 
  6. } 

在上例中我們判斷第一位是否為 1，所以如果要判斷第 n 位是否 1，只要把 1 左移 n 位再作與運(yùn)算不就完了。

3、將第 n 位設(shè)置為 1

  1. y = x | (1<<n) 

思路同第二步，先把 1 移到第 n 位再作或運(yùn)算，這樣第 n 位就肯定為 1。

4、將第 n 位設(shè)置為 0

  1. y = x & ~(1< 

先將 1 左移到 第 n 位，再對(duì)其取反，此時(shí)第 n 位為 0，其他位都為 1，這樣與 x 作與運(yùn)算后，x 的第 n 位肯定為 0。

5、將第 n 位的值取反

  1. y = x ^ (1< 

我們知道異或操作是兩個(gè)數(shù)的每一位相同，結(jié)果為 0，否則是 1，所以現(xiàn)在把 1 左移到第 n 位，則如果 x 的第 n 位為 1，兩數(shù)相同結(jié)果 0，如果 x 的第 n 位為 0，兩數(shù)不相同，則為 1。來(lái)看個(gè)簡(jiǎn)單的例子

  1. 01110101 
  2.   00100000 
  3.   -------- 
  4.   01010101 

如圖示，第五位剛好取反

6、將最右邊的 1 設(shè)為 0

  1. y = x & (x-1) 

如果說(shuō)上面的 5 點(diǎn)技巧有點(diǎn)無(wú)聊，那第 6 條技巧確實(shí)很有意思，也是在 leetcode 經(jīng)常出現(xiàn)的考點(diǎn)，下文中大部分習(xí)題都會(huì)用到這個(gè)知識(shí)點(diǎn)，務(wù)必要謹(jǐn)記!掌握這個(gè)很重要，有啥用呢，比如我要統(tǒng)計(jì) 1 的位數(shù)有幾個(gè)，只要寫(xiě)個(gè)如下循環(huán)即可，不斷地將 x 最右邊的 1 置為 0，最后當(dāng)值為 0 時(shí)統(tǒng)計(jì)就結(jié)束了。

  1. count = 0   
  2. while(x) { 
  3.   x = x & (x - 1); 
  4.   count++; 
  5. } 

先介紹這么多吧，如果大家對(duì)其他的位運(yùn)算技巧感興趣可以看看文末的參考鏈接

巧用位運(yùn)算解算法題

接下來(lái)我們看看位運(yùn)算在算法題中的應(yīng)用。

1、高頻面試題：老鼠試毒

有 8 個(gè)一模一樣的瓶子，其中有 7 瓶是普通的水，有一瓶是毒藥。任何喝下毒藥的生物都會(huì)在一星期之后死亡?，F(xiàn)在，你只有 3 只小白鼠和一星期的時(shí)間，如何檢驗(yàn)出哪個(gè)瓶子里有毒藥?

解題步驟如下：

（1）把這 8 個(gè)瓶子從 0 到 7 進(jìn)行編號(hào)，用二進(jìn)制表示如下

  1. 000 
  2. 001 
  3. 010 
  4. 011 
  5. 100 
  6. 101 
  7. 110 
  8. 111 

（2）將 0 到 7 編號(hào)中第一位為 1 的所有瓶子(即 1，3，5，7)的水混在一起給老鼠 1 吃，第二位值為 1 的所有瓶子(即2，3，6，7)的水混在一起給老鼠 2 吃， 第三位值為 1 的所有瓶子(4，5，6，7)的水混在一起給老鼠 3 吃，現(xiàn)在假設(shè)老鼠 1，3 死了，那么有毒的瓶子編號(hào)中第 1，3 位肯定為 1，老鼠 2 沒(méi)死，則有毒的瓶子編號(hào)中第 2 位肯定為 0，得到值 101 ，對(duì)應(yīng)的編號(hào)是 5， 也就是第五瓶的水有毒。

這道題及其相關(guān)的變種在面試中出現(xiàn)地比較頻繁，比如我現(xiàn)在把 8 瓶水換成 1000 瓶，問(wèn)你至少需要幾只老鼠才能測(cè)出有毒的瓶子，有了上述的思路相信應(yīng)該不難，幾只老鼠就相當(dāng)于幾個(gè)進(jìn)制位，顯然 2^10 = 1024 > 1000，即 10 只老鼠即可測(cè)出來(lái)。

2、leetcode 232

給定一個(gè)數(shù)，判斷它是否是可以用 2 的冪次方表示，可以返回 true，不可以返回 false，比如 8 = 2^3, 說(shuō)明可以用 2 的冪次方表示，返回 true，9 不可以，所以返回 false。

解題分析：這題常規(guī)解法是做個(gè)循環(huán)不斷地乘以 2 ，看下是否等于給定的值，如果等于說(shuō)明是 2 的冪次方，否則如果不斷累乘 2 后大于給定的值，說(shuō)明不能用 2 的冪次方表示，時(shí)間復(fù)雜度是所做的累乘的次數(shù)，即 2^n >= 給定的值中的 n。

那是否有更快的解法呢?

上文的介紹中其實(shí)我們已經(jīng)埋下伏筆了，沒(méi)錯(cuò)用 x & (x-1)，首先我們要發(fā)現(xiàn)能用 2 的冪次方表示的數(shù)的特點(diǎn)：它的所有位中有且僅有一位為 1，如

  1. 00001        2^0 = 1 
  2. 00010        2^1 = 2 
  3. 00100        2^2 = 4 
  4. 01000        2^3 = 8 
  5. 10000        2^3 = 16 

如圖示，所有 2 的冪次方最多只有一位為 1

明白了這一點(diǎn)， 我們的思路就簡(jiǎn)單了，由于符合 2 的冪次方的數(shù)只有一位為 1，x & (x-1) 是把最后一位 1 置為 0，所以只要做一次 x & (x-1) 運(yùn)算，看它的值是否等于 0 即可，如果是 0 說(shuō)明它可以用 2 的冪次方表示，否則不可以，代碼如下:

  1. if(x&(x-1)) { //使用與運(yùn)算判斷一個(gè)數(shù)是否是2的冪次方 
  2.     printf("%d不是2的冪次方！\n", num); 
  3. } else { 
  4.     printf("%d是2的%d次方！\n", num, log2(num)); 
  5. } 

只用一行代碼即可搞定，方便了很多!

3、leetcode 232

給定一個(gè)非負(fù)整數(shù) num. 對(duì)于 0 ≤ i ≤ num 范圍中的每個(gè)數(shù)字 i, 計(jì)算其二進(jìn)制數(shù)中 1 的數(shù)目并將它們作為數(shù)組返回。輸入: 5 輸出: [0,1,1,2,1,2]

這題的常規(guī)解法相信大家都能猜到，就是從 0 到 num 循環(huán)一遍，求出每個(gè)數(shù)字 i 中 1 的數(shù)目。

如果用位運(yùn)算怎么做呢，先來(lái)看下解法，然后我們?cè)賮?lái)分析為啥這樣寫(xiě)，非常巧妙!

Python 代碼

  1. vector<int> countBits(int num) { 
  2.     vector<int> bits(num+1, 0); 
  3.     for (int i = 1; i<= num; i++) { 
  4.         bits[i] += bits[i & (i-1)] + 1; 
  5.     } 
  6. } 

Java 代碼

  1. public static int[] countBits(int num) { 
  2.     int[] bits = new int[num+1]; 
  3.     Arrays.fill(bits, 0); 
  4.  
  5.     for (int i = 1; i <= num; i++) { 
  6.         bits[i] = bits[i & (i-1)] + 1; 
  7.     } 
  8.     return bits; 
  9. } 

最關(guān)鍵的代碼看這一行

  1. bits[i] += bits[i & (i-1)] + 1; 

這行代碼是啥意思呢，i & (i-1) 是把 i 的最后一個(gè)值為 1 的位設(shè)為 0，不難發(fā)現(xiàn)整數(shù)「i & (i-1)」 中 1 的位數(shù)比 i 中 1 的位數(shù)少一個(gè) ，所以要加 1(即 bits[i & (i-1)] + 1)。非常巧妙，這樣從 1 開(kāi)始走一遍循環(huán)即可，中間不要做任何針對(duì)變量 i 的 1 的個(gè)數(shù)的計(jì)算，只不過(guò)付出了一個(gè) bits 數(shù)組的代價(jià)。這里也是利用了以空間換時(shí)間的思想。

4、利用位運(yùn)算來(lái)解八皇后問(wèn)題

接下來(lái)我們來(lái)看看終級(jí) Boss 題，如何用位運(yùn)算來(lái)解八皇后問(wèn)題，解題中運(yùn)用到了非常多的位運(yùn)算技巧，相信你學(xué)完會(huì)收獲不少。

在 8×8 格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法

舉個(gè)簡(jiǎn)單的下圖所示的例子，如果在棋盤(pán)上放置一個(gè)皇后，則與這個(gè)皇后同一行，同一列，且皇后所在斜線經(jīng)過(guò)的格子不能再放其他皇后。

如圖示，在其中任意一行放置一個(gè)皇后，則與此皇后同行，同列，同對(duì)角線的都不允許再放其他皇后，圖中藍(lán)色區(qū)塊不允許放其他皇后。

一般我們用回溯法解八皇后。這里簡(jiǎn)單介紹一下啥是回溯法。

在第一行從左到右先選擇一個(gè)位置放置皇后，由于第一行放了皇后，第二行可放皇后的位置受到了限制(下圖藍(lán)色區(qū)塊表示對(duì)應(yīng)行的格子不能放皇后)

如圖示,第二行放皇后的位置只能從第三個(gè)格子開(kāi)始選

第二行我們選第三個(gè)格子放皇后，選完開(kāi)始在第三行選，第三方可選的位置也受到了第一，二行皇后所放位置的影響

如圖示，第三行只能從第五個(gè)格子開(kāi)始放置皇后

同理，第三，四，五行都從左到右選擇符合條件的的格子放置皇后，選完后問(wèn)題來(lái)了，第六行所在行沒(méi)有可選的位置了!如圖示

怎么辦呢，回溯!重新擺放第五行的皇后，將其放到第八格上

重新擺放后發(fā)現(xiàn)第六行還是沒(méi)有符合條件的格子，咋辦，我們知道第六行可擺放皇后的格子受第五行影響，而第五行受第四行擺放皇后位置的影響的，所以回溯到第四行，將皇后位置擺放到當(dāng)前行的其他位置(第七格)，再接著往下放 5，6，7，8 行的皇后。。。，只要不滿足條件，改變上一層的的條件重新來(lái)，上一層調(diào)整后還是不符合條件，再調(diào)整上上層的。。。，調(diào)整完后重新往下遞歸選擇，直到找到符合條件的，找到之后再在第一層換一個(gè)位置選皇后遞歸往下層選擇執(zhí)行，直到找到所有的解，這種不滿足條件就回退上層調(diào)整再試的思想就是回溯法，可以看到回溯法一般是用遞歸實(shí)現(xiàn)的。

回溯算法有不少變種，這里我們重點(diǎn)介紹使用位運(yùn)算的回溯算法，它是所有解法中最高效的!如果在面試中能使用位運(yùn)算來(lái)解回溯算法，絕對(duì)會(huì)讓面試官給你個(gè)大大的贊!

接下來(lái)是重點(diǎn)了，怎么用位運(yùn)算來(lái)求解。

在以上回溯法的分析中，我們不難發(fā)現(xiàn)，在八皇后問(wèn)題中，問(wèn)題的關(guān)鍵是找出行可放皇后的格子。找到之后問(wèn)題就解決了 90%，所以接下來(lái)我們就來(lái)看看怎么找這些可用的格子。

假設(shè)我們要求解第三行可放皇后的格子(說(shuō)明一二行的皇后已放好了)那么第三行可放皇后的位置受到哪些條件的限制呢。顯然在第一二行已放皇后的格子所在的列，左斜線，右斜線對(duì)應(yīng)的方格都不能放皇后，如圖示:

我們以 column 來(lái)記錄所有上方行已放置的皇后導(dǎo)致當(dāng)前行格子不可用的集合，所在列如果放了皇后，則當(dāng)前行格子對(duì)應(yīng)的位置為 1，否則為 0，同理,以 pie(撇，左斜線) 記錄所有已放置的皇后左斜方向?qū)е庐?dāng)前行格子不可用的集合， na(捺，右斜線) 表示所有已放置的皇后右斜方向?qū)е庐?dāng)前行不可用的集合。則對(duì)于第三行來(lái)說(shuō)我們有：

  1. column = 10010000 (上圖中的第一個(gè)圖，第 1，4 列放了皇后，所以 1，4 位置為 1，其他位置為 0） 
  2. pie = 00100000 (上圖中的第二個(gè)圖，左斜線經(jīng)過(guò)第三行的第三個(gè)方格，所以第三位為 1） 
  3. na = 00101000 (上圖中的第三個(gè)圖，右斜線經(jīng)過(guò)第三行的第三, 五個(gè)方格，所以第三,五位為 1） 

將這三個(gè)變量作或運(yùn)算得到結(jié)果如下

  1.  10010000 
  2. |   00100000 
  3. |   00101000 
  4. ----------------------- 
  5.     10111000 

也就是說(shuō)對(duì)于第三層來(lái)說(shuō)第 1，3，4，5 個(gè)格子不能放皇后。如圖示

于是可知 column | pie | na 得到的結(jié)果中值為 0 的代表當(dāng)前行對(duì)應(yīng)的格子可放皇后， 1 代表不能放，但我們想改成 1 代表格子可放皇后， 0 代表不可放皇后，畢竟這樣更符合我們的思維方式，怎么辦，取反不就行了，于是我們有~(column| pie | na)。

問(wèn)題來(lái)了，這樣取反是有問(wèn)題的，因?yàn)檫@三個(gè)變量都是定義的 int 型，為 32 位，取反之后高位的 0 全部變成了 1，而我們只想保留低 8 位(因?yàn)槭?8 皇后)，想把高位都置為 0，怎么辦，這里就要用到位運(yùn)算的黑科技了

  1. ~(column | pie | na) & ((1 << 8)-1) 

后面的的 ((1<< 8) -1) 表示先把 1 往左移 8 位，值為 100000000,再減 1 ，則低 8 位全部為 1，高位全部為 0!(即 0011111111)再作與運(yùn)算，即可保留低 8 位，去除高位。

費(fèi)了這么大的勁，我們終于把當(dāng)前行可放皇后的格子都找出來(lái)了(所有位值為 1 的格子可放置皇后)。接下來(lái)我們只要做個(gè)循環(huán)，遍歷所有位為 1 的格子，每次取出可用格子放上皇后，再找下一層可放置皇后的格子，依此遞歸下去即可,直到所有行都遍歷完畢(遞歸的終止條件)。

還有一個(gè)問(wèn)題，已知當(dāng)前行的 column，pie，na，怎么確定下一行的 column，pie，na 的值(畢竟選完當(dāng)前行的皇后后，要確定下一行的可用格子，而下一行的可用格子依賴于 column，pie，na 的值)

上文可知，我們已經(jīng)選出了當(dāng)前行可用的格子(相應(yīng)位為 1 對(duì)應(yīng)的格子可用)，假設(shè)我們?cè)诋?dāng)前行選擇了其中一個(gè)格子來(lái)放置皇后，此位置記為 p(如果是當(dāng)前行的最后一個(gè)格子最后一個(gè)格子，則值為 1，如果放在倒數(shù)第二個(gè)，值為 10，倒數(shù)第三個(gè)則為 100，依此類(lèi)推)，則對(duì)于下一行來(lái)說(shuō)，顯然 column = column | p

那么 pie 呢，仔細(xì)看下圖，顯然應(yīng)該為 (pie | p) << 1, 左斜線往下一行的格子延展時(shí)，相當(dāng)于左移一位，

如圖示：下一行的 pie 顯然為 (pie | p) << 1。

同理 下一行的 na 為 (na | p) >> 1。

有了以上詳細(xì)地解析，我們就可以寫(xiě)出偽代碼了

  1. void queenSettle(row, colomn,pie,na) { 
  2.     N = 8; // 8皇后 
  3.     if (row >= N) { 
  4.         // 遍歷到最后一行說(shuō)明已經(jīng)找到符合的條件了 
  5.         count++;return 
  6.     } 
  7.  
  8.         // 取出當(dāng)前行可放置皇后的格子 
  9.     bits = (~(colomn|pie|na)) & ((1 << N)-1) 
  10.  
  11.     while(bits > 0) { 
  12.             // 每次從當(dāng)前行可用的格子中取出最右邊位為 1 的格子放置皇后 
  13.             p = bits & -bits 
  14.  
  15.             // 緊接著在下一行繼續(xù)放皇后 
  16.             queenSettle(row+1, colomn | p, (pie|p) << 1, (na | p) >> 1) 
  17.  
  18.             // 當(dāng)前行最右邊格子已經(jīng)選完了，將其置成 0，代表這個(gè)格子已遍歷過(guò) 
  19.             bits = bits & (bits-1) 
  20.     } 
  21. } 

一開(kāi)始傳入 queenSettle(0,0,0,0) 這樣即可得到最終的解。偽代碼寫(xiě)得很清楚了，相信用相關(guān)語(yǔ)言不難實(shí)現(xiàn)，這里就留給大家作個(gè)練習(xí)吧。

總結(jié)

本文帶大家由淺入深地完成了位運(yùn)算的學(xué)習(xí)，掌握好位運(yùn)算不僅僅是為了提升逼格，還能極大地提升效率，位運(yùn)算也廣泛地應(yīng)用于代碼編寫(xiě)中，運(yùn)用得當(dāng)能極大地簡(jiǎn)化代碼，且可讀性更好，限于篇幅關(guān)系，這里不展開(kāi)，大家如有興趣可參考文末的鏈接。

如有幫助，歡迎大家關(guān)注公號(hào)哦。之后將會(huì)講解大量算法的解題思路，希望我們一起攻克算法難題!

 

責(zé)任編輯：武曉燕 來(lái)源： 碼海
位運(yùn)算操作技巧
相關(guān)推薦

2022-08-01 08:12:14

位運(yùn)算代碼性能

2009-06-18 13:06:59

C#位運(yùn)算權(quán)限管理

2022-05-18 16:06:15

位運(yùn)算異或運(yùn)算

2022-05-23 15:02:19

異或運(yùn)算面試真題

2021-11-09 14:08:45

DockerDockerfileJava

2021-02-21 06:36:57

運(yùn)算技巧按位

2011-08-29 15:53:04

Lua位運(yùn)算

2021-01-23 12:22:59

位運(yùn)算編程語(yǔ)言開(kāi)發(fā)

2023-04-07 08:02:54

源碼位邏輯運(yùn)算符

2022-08-01 08:36:09

upstream下游上游

2009-07-31 16:48:44

C#位運(yùn)算

2021-10-11 09:41:20

React位運(yùn)算技巧前端

2021-10-11 19:01:47

CPU位運(yùn)算JS

2015-09-10 16:06:06

32位64位Windows 10

2018-04-25 08:14:36

霧計(jì)算云計(jì)算物聯(lián)網(wǎng)

2018-04-25 15:53:12

霧計(jì)算

2021-04-23 21:03:10

MySQL數(shù)據(jù)語(yǔ)法

2009-08-12 10:20:52

C#位運(yùn)算符

2019-05-28 14:33:07

Javascript運(yùn)算符前端

2020-06-18 09:04:59

CC++程序
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)