2.位運算 · java核心知識整理

作者：力扣（LeetCode）鏈接：https://www.zhihu.com/question/38206659/answer/736472332 來源：知乎著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。計算機中的數在內存中都是以二進制形式進行存儲的，用位運算就是直接對整數在內存中的二進制位進行操作，因此其執行效率非常高，在程序中盡量使用位運算進行操作，這會大大提高程序的性能。 ## **位操作符** * & 與運算兩個位都是 1 時，結果才為 1，否則為 0，如 1 0 0 1 1 & 1 1 0 0 1 `------------------------------` 1 0 0 0 1 * | 或運算兩個位都是 0 時，結果才為 0，否則為 1，如 1 0 0 1 1 | 1 1 0 0 1 `------------------------------` 1 1 0 1 1 * ^ 異或運算，兩個位相同則為 0，不同則為 1，如 1 0 0 1 1 ^ 1 1 0 0 1 `-----------------------------` 0 1 0 1 0 * ~ 取反運算，0 則變為 1，1 則變為 0，如 ~ 1 0 0 1 1 `-----------------------------` 0 1 1 0 0 ? * << 左移運算，向左進行移位操作，高位丟棄，低位補 0，如 ~~~text int a = 8; a << 3; 移位前：0000 0000 0000 0000 0000 0000 0000 1000 移位后：0000 0000 0000 0000 0000 0000 0100 0000 ~~~ \>> 右移運算，向右進行移位操作，對無符號數，高位補 0，對于有符號數，高位補符號位，如 ~~~text unsigned int a = 8; a >> 3; 移位前：0000 0000 0000 0000 0000 0000 0000 1000 移位后：0000 0000 0000 0000 0000 0000 0000 0001 ? int a = -8; a >> 3; 移位前：1111 1111 1111 1111 1111 1111 1111 1000 移位前：1111 1111 1111 1111 1111 1111 1111 1111 ~~~ ## **常見位運算問題** ### 1\. 位操作實現乘除法 * 數 a 向右移一位，相當于將 a 除以 2；數 a 向左移一位，相當于將 a 乘以 2 ~~~text int a = 2; a >> 1; ---> 1 a << 1; ---> 4 ~~~ ### 2\. 位操作交貨兩數 * 位操作交換兩數可以不需要第三個臨時變量，雖然普通操作也可以做到，但是沒有其效率高 ~~~text //普通操作 void swap(int &a, int &b) { a = a + b; b = a - b; a = a - b; } //位與操作 void swap(int &a, int &b) { a ^= b; b ^= a; a ^= b; } ~~~ 位與操作解釋：第一步：a ^= b ---> a = (a^b); 第二步：b ^= a ---> b = b^(a^b) ---> b = (b^b)^a = a 第三步：a ^= b ---> a = (a^b)^a = (a^a)^b = b ### 3\. 位操作判斷奇偶數 * ?只要根據數的最后一位是 0 還是 1 來決定即可，為 0 就是偶數，為 1 就是奇數。 ~~~text if(0 == (a & 1)) { //偶數 } ~~~ ### 4\. 位操作交換符號 * 交換符號將正數變成負數，負數變成正數 ~~~text int reversal(int a) { return ~a + 1; } ~~~ 整數取反加1，正好變成其對應的負數(補碼表示)；負數取反加一，則變為其原碼，即正數 ### 5\. 位操作求絕對值 * 整數的絕對值是其本身，負數的絕對值正好可以對其進行取反加一求得，即我們首先判斷其符號位（整數右移 31 位得到 0，負數右移 31 位得到 -1,即 0xffffffff），然后根據符號進行相應的操作 ~~~text int abs(int a) { int i = a >> 31; return i == 0 ? a : (~a + 1); } ~~~ 上面的操作可以進行優化，可以將 i == 0 的條件判斷語句去掉。我們都知道符號位 i 只有兩種情況，即 i = 0 為正，i = -1 為負。對于任何數與 0 異或都會保持不變，與 -1 即 0xffffffff 進行異或就相當于對此數進行取反,因此可以將上面三目元算符轉換為((a^i)-i)，即整數時 a 與 0 異或得到本身，再減去 0，負數時與 0xffffffff 異或將 a 進行取反，然后在加上 1，即減去 i(i =-1) ~~~text int abs2(int a) { int i = a >> 31; return ((a^i) - i); } ~~~ ### 6\. 位操作進行高低位交換 * 給定一個 16 位的無符號整數，將其高 8 位與低 8 位進行交換，求出交換后的值，如： ~~~text 34520的二進制表示： 10000110 11011000 將其高8位與低8位進行交換，得到一個新的二進制數： 11011000 10000110 其十進制為55430 ~~~ 從上面移位操作我們可以知道，只要將無符號數 a>>8 即可得到其高 8 位移到低 8 位，高位補 0；將 a>8 和 a<<8 進行或操作既可求得交換后的結果。 ~~~text unsigned short a = 34520; a = (a >> 8) | (a << 8); ~~~ ### 7\. 位操作進行二進制逆序將無符號數的二進制表示進行逆序，求取逆序后的結果，如 ~~~text 數34520的二進制表示： 10000110 11011000 逆序后則為： 00011011 01100001 它的十進制為7009 ~~~ 在字符串逆序過程中，可以從字符串的首尾開始，依次交換兩端的數據。在二進制中使用位的高低位交換會更方便進行處理，這里我們分組進行多步處理。 * 第一步:以每 2 位為一組，組內進行高低位交換 ~~~text 交換前： 10 00 01 10 11 01 10 00 交換后： 01 00 10 01 11 10 01 00 ~~~ * 第二步：在上面的基礎上，以每 4 位為 1 組，組內高低位進行交換 ~~~text 交換前： 0100 1001 1110 0100 交換后： 0001 0110 1011 0001 ~~~ * 第三步：以每 8 位為一組，組內高低位進行交換 ~~~text 交換前： 00010110 10110001 交換后： 01100001 00011011 ~~~ * 第四步：以每16位為一組，組內高低位進行交換 ~~~text 交換前： 0110000100011011 交換后： 0001101101100001 ~~~ 對于上面的第一步，依次以 2 位作為一組，再進行組內高低位交換，這樣處理起來比較繁瑣，下面介紹另外一種方法進行處理。先分別取原數 10000110 11011000 的奇數位和偶數位，將空余位用 0 填充： ~~~text 原數： 10000110 11011000 奇數位： 10000010 10001000 偶數位： 00000100 01010000 ~~~ 再將奇數位右移一位，偶數位左移一位，此時將兩個數據相或即可以達到奇偶位上數據交換的效果： ~~~text 原數： 10000110 11011000 奇數位右移一位： 0 10000010 1000100 偶數位左移一位：0000100 01010000 0 兩數相或得到： 01001001 11100100 ~~~ 上面的方法用位操作可以表示為： * 取a的奇數位并用 0 進行填充可以表示為：a & 0xAAAA * 取a的偶數為并用 0 進行填充可以表示為：a & 0x5555 因此，上面的第一步可以表示為： a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1) 同理，可以得到其第二、三和四步為： a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2) a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4) a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8) 因此整個操作為： ~~~text unsigned short a = 34520; a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1); a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2); a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4); a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8); ~~~ ### 8\. 位操作統計二進制中 1 的個數統計二進制1的個數可以分別獲取每個二進制位數，然后再統計其1的個數，此方法效率比較低。這里介紹另外一種高效的方法，同樣以 34520 為例，我們計算其 a &= (a-1)的結果： * 第一次：計算前：1000 0110 1101 1000 計算后：1000 0110 1101 0000 * 第二次：計算前：1000 0110 1101 0000 計算后：1000 0110 1100 0000 * 第二次：計算前：1000 0110 1100 0000 計算后：1000 0110 1000 0000 我們發現，沒計算一次二進制中就少了一個 1，則我們可以通過下面方法去統計： ~~~text count = 0 while(a){ a = a & (a - 1); count++; } ~~~