位運算使用技巧及巧解演算法題
- 2020 年 4 月 9 日
- 筆記
位運算使用技巧及巧解演算法題
位運算
簡單的複習一下基本的位運算，這些使用技巧在下面都有用到。
// 按位與 & , 雙1得1, 其他都得0，使用：比如設置某些位為0，或者取某些位 // 按位或 | ， 單1即可得1， 只有雙0才得0，使用：比如設置某些位為1 // 異或 ^ ， 相同則為0，相反則為1，即 10相碰得1，使用：比如取某些位的相反位 //下面這四個一般用來構造某些特殊的二進位數 // 按位取反 ~ 很簡單，取反即可 // 左移 << 把數向左移，右邊空出來的補0 // （無符號數）邏輯右移 >> 把數往右移，左邊空出來的補0，注意在C中只有無符號數才如此 // （有符號數）算術右移 >> 把數往右移，左邊空出來的補符號位，即正數補0，負數補1，有符號數執行的是算術運算 // 在其他語言中可能有不同，比如Java中算術右移和邏輯右移就是不同的運算符： >>和>>> 簡單技巧
- 判斷整型的奇偶
if (x & 1) // 奇數 else // 偶數 - 將一個數符號取反，即取相反數
int x; x = ~x+1; //相反數 - 判斷第n位是否設置為1
if (x & (1 << n)) // 是 else // 否 - 將第n位設置為1
x = x | (1 << n); - 將第n位設置為0
x = x & ~ (1 << n); - 將第n位取反
x = x ^ (1 << n); - 【】將最右邊的1設為0
x = x & (x-1); 【重要技巧】即可得到比當前數二進位少1的數（且數值恰比當前數小）
- 設置第n到m位為1（最左邊為第0位）以下皆利用宏來實現
#define SETBITS1(x, n, m) (x) | ((~(0U)<<(sizeof(x)-(m-n+1)))>>n) 【注】：((~(0U)<<(sizeof(x)-(m-n+1)))>>n)是得到第n位到第m位為1，其他位為0，如00...000111111110000000...的形式
- 設置第n到m位為0
#define SETBITS0(x, n, m) (x) & ~((~(0U)<<(sizeof(x)-(m-n+1)))>>n) - 取第n到m位
#define GETBITSN_M(x, n, m) (x) & ((~(0U)<<(sizeof(x)-(m-n+1)))>>n) - 取第n到m位的相反位
#define GET_REVERSE_BITS(x, n, m) (x) ^ ((~(0U)<<(sizeof(x)-(m-n+1)))>>n) 巧用位運算解演算法題
- 老鼠試毒問題
有8個一模一樣的瓶子，其中有7瓶是水，一瓶是毒藥。任何喝下毒藥的生物都會在一個星期之內死亡。現在你有三隻老鼠和一星期的時間，如何檢驗哪個瓶子里是毒藥？
【解】
1）把8個瓶子進行編號，0-7，使用二進位表示，如下：
000 001 010 011 100 101 110 111 2）將第一位是1的瓶子里的液體混合餵給第一隻老鼠吃，將第二位是1的瓶子里的液體餵給第二隻老鼠吃，將第三位是1的瓶子里的液體餵給第三隻老鼠吃。之後即可根據老鼠的死亡情況確定是那一瓶液體有毒。
如：第1、3隻老鼠死亡。即第一位、第三位是1的瓶子里必有毒，第二位是0，即為101瓶子里是毒藥。
【總結】：老鼠即為所需的二進位位，假如現有1000瓶水，問你至少需要幾隻老鼠才能測出有毒的瓶子？2^10 = 1024 > 1000
- Leetcode 232
給定一個數，判定他是否可以用2的冪次方來表示，可以返回true，不可以返回false
【常規解法】不斷用2去除，或者從1 乘到大於等於該數為止。O(logn)
【解】如果一個數是2的冪次方，則它必定可以表示為100....的形式，當然，0也可以，所以該數的二進位表示至多有一個1。則可以利用之前的將最後一個1設置為0的技巧，循環遍歷至x為0為止。O(1)
int is2Power(int x) { int y = abs(x); y &= (y-1); // 0也可以使用 if (!y) return 1; else return 0; } - Leetcode 232
給定一個非負整數num， 對於0<=i<=num範圍中的每個數字i，計算其二進位數中1的數目並將它們作為數組返回。
【常規解法】對每個數字調用函數計算二進位數的數目。
【解】利用x&(x-1)這個數比x的二進位位1的數目少1個
int bits[MAX] = {0}; int countBits(int num) { int i; for (i = 1; i <= num; i++) bits[i] = bits[i&(i-1)]+1; } -
求解八皇后問題
八皇后問題，待補充解釋說明
void queenSettle(row, colomn, Lline, Rline) { int count = 0; //column二進位表示，1代表當前列之前行已經放置了棋子，不可再放棋子 //Lline和Rline，表示之前行放置的棋子的左斜行和右斜行的位置，不可再放棋子 int N = 8; // 8皇后問題 if (row > = N) { //遍歷到最後一行，最後一行無需在找，只需找到空的那一列即可，說明已經找到了符合的解法 count++; return ; } // 取出當前行可放置皇后的格子 bits = ~((column|Lline|Rline)) & ((1 << N)-1); //按位與是只取後N位，取反是為了保證將原來0表示可以放置棋子變成1可以放置棋子 while(bits > 0) { //每次從當前行可用的格子中取出最右邊位為1的格子放置皇后 p = bits & -bits; //緊接著在下一行繼續放皇后 queenSettle(row+1, column|p, (Lline|p) << 1, (Rline|p) >> 1) //當前行最右邊的格子已經選完了，將其置為0，表示已經這個格子已經遍歷過 bits = bits & (bits-1); } } 
