位操作的個人總結
在計算機中所有資料都是以二進位制形式進行儲存,而位運算就是直接對記憶體中的二進位制資料進行操作,因此處理速度非常快。
1. 基本操作
運算子 | 用法示例 | 運算規則 |
按位與 AND | a & b | 只有兩個運算元相應的位元位都為1時,結果才為1,否則為0 |
按位或 OR | a | b | 只有兩個運算元相應的位元位都為0時,結果才為0,否則為1 |
按位異或 XOR | a ^ b | 兩個運算元相應位元位不相同時,結果為1,否則為0 |
按位取反 NOT | ~a | 運算元相應位元位取反,0變為1, 1變為0 |
左移 | a << b | 將a的二進位制形式向左移b個bit,右側填充0 |
右移 | a >> b | 將a的二進位制形式向右移b個bit,有符號數邏輯移位,無符號數算術移位 |
C/C++中移位運算包含邏輯移位(Logical shift)和算術移位(Arithmetic shift)兩種,其中邏輯移位的意思是,移出去的位直接捨棄,空缺位用0填充;算術移位的意思是,移出去的位直接捨棄,空缺位用符號位填充。
- 對於無符號數,無論是左移還是右移都是邏輯移位,如0011 0110 左移兩位結果為1101 1000,右移兩位結果為0000 1101。
- 對於有符號數,左移仍然是邏輯移位,右移則略有不同,進行的是算術移位,如1011 0110 左移兩位結果為1101 1000,右移兩位結果為1110 1101(前面兩位填充的是符號位1)。
2. 常見應用
對n的指定位進行操作,其它位保持不變。
1 n &= ~(1 << 5);// 1左移5位得到 0010 0000, 按位取反得 1101 1111,與n按位與使其第6位被清零,其它位不變 2 n |= (1 << 5);// 1左移5位得到 0010 0000, 與n按位或使其第6位被置1,其它位不變 3 n ^= (1 << 5);// 將n第6位取反,其它位不變
判斷給定正整數n的奇偶
1 1 bool flag = a & 1; // a對應二進位制數末位為0則為偶數,否則為奇數。相比 bool flag = (a % 2 == 0); 運算速度快了很多。
判斷n是否為2的正整數次冪
1 /*=============================================================================================== 2* 將2的次冪寫成二進位制容易發現,二進位制中只有一個1,後面跟了n個0。 3* 如果將這個數減1,僅有的一個1變成了0,後面的n個0變成了1。時間複雜度O(1)。 4*=============================================================================================== */ 5 bool isPowerOfTwo(int n) { 6return (n & (n - 1)== 0); 7 }
1 /*============================================================================================== 2* 常規思路:利用迴圈判斷n是否能被2整除,如果是除以2,繼續迴圈。 3* 最終結果若為1則表明其是2的正整數次冪,否則不是。時間複雜度O(log n)。 4*============================================================================================== 5*/ 6 bool isPowerOfTwo(int n) { 7while (n % 2 ==0) { 8n /= 2; 9} 10return (n == 1); 11 }
統計給定正整數的二進位制中1的個數
1 /*============================================================================================== 2* 與上述判斷n是否為2的正整數次冪時相似,n&(n -1) 作用是將n的二進位制中最右邊的1置為0,如此迴圈以統計n中1的個數 3*============================================================================================== 4*/ 5 int count1Bit(int n) { 6int countOneBit= 0; 7while (n) { 8countOneBit ++; 9n &= n -1; 10} 11return countOneBit; 12 }
1 /*============================================================================================== 2* 另一種四步分組法,以34520(1000011011011000)為例 3* 第一步:每2位為一組,組內高低位相加。 4* 10 00 01 10 11 01 10 00 -> 01 00 01 01 10 01 01 00 5* (10高位為1,低位為0,相加得01;11高位為1,低位也為1,相加得10……)。 6* 第二步:將第一步得到的結果每4位分為一組,組內高低位相加。 7* 0100 0101 1001 0100 -> 0001 0010 0011 0001 8* (0100高位為01低位為00,相加得01;1001高位為10低位為01,相加得11……)。 9* 第三步:將第二步得到的結果每8位分為一組,組內高低位相加。 10* 00010010 00110001 -> 00000011 00000100。 11* 第四步:將第三步得到的結果每16位分為一組,組內高低位相加。 12* 0000001100000100 -> 00000111。 13* 這樣最後得到的結果7即為給定整數中1的個數。 14*============================================================================================== 15*/ 16 int count1Bit(int n) { 17n = ((n & 0xAAAA) >> 1) + (n & 0x5555); 18n = ((n & 0xCCCC) >> 2) + (n & 0x3333); 19n = ((n & 0xF0F0) >> 4) + (n & 0x0F0F); 20n = ((n & 0xFF00) >> 8) + (n & 0x00FF); 21return n; 22 }
不需要額外變數交換兩個整數的值
1 void Swap(int &m, int &n) { 2if ( m != n ) { 3m ^= n;// m = (m ^ n) 4n ^= m;// n = n ^ (m ^ n) = n ^ m ^ n = n ^ n ^ m =m, 一個數和自身異或結果為0,一個數和0異或結果為其自身 5m ^= n;// m = m ^ n = m ^ n ^ m = n 6} 7 }
1 void Swap(int &m, int &n) { 2if ( m != n ) { 3int temp = a;// 常規思路:藉由中間變數實現交換。 4a = b; 5b = temp; 6} 7 }
16位無符號整型數高低位交換
1 /*========================================================================================= 2* 對於16位無符號整型資料,分為高8位和低8位,高八位右移時高位填充0,低八位左移時末位填充0,將兩者相加即可。 3*========================================================================================= 4*/ 5 unsigned int lowHighExchange(unsigned int n) { 6return ((a >> 8) + (a << 8)); 7 }
二進位制逆序操作
1 /*======================================================================================== 2* 通過四步分組法得到16位整型資料的二進位制逆序。以34520(1000 0110 1101 1000)為例, 3* 第一步:每2位為一組,組內高低位交換。 4* 10 00 01 10 11 01 10 00->01 00 10 01 11 10 01 00。 5* 第二步:每4位為一組,組內高低位交換。0100 1001 1110 0100 -> 0001 0110 1011 0001。 6* 第三步:每8位為一組,組內高低位交換。00010110 10110001 -> 01100001 00011011。 7* 第四步:每16位為一組,組內高低位交換。0110000100011011 -> 00011011 01100001。 8* 改進:對第一步先分別取原資料的奇數位和偶數位 9* 空位以下劃線表示:1_0_0_1_1_0_1_0_, _0_0_1_0_1_1_0_0, 10* 將下劃線填充0得原數 1000 0110 1101 1000 11* 奇數位 1000 0010 1000 1000, 偶數位 0000 0100 0101 0000 12* 再將奇數位右移一位,偶數位左移一位,將移位後的兩數按位或可使奇偶位資料交換。 13* 原數 1000 0110 1101 1000, 奇數位右移一位 0100 0001 0100 0100 14* 偶數位左移一位 0000 1000 1010 0000,按位或得 0100 1001 1110 0111 15*======================================================================================= 16*/ 17 int binaryReverse( int n ) { 18n = ((n & 0xAAAA) >> 1) | ((a & 0x5555) << 1); 19n = ((n & 0xCCCC) >> 2) | ((a & 0x3333) << 2); 20n = ((n & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4); 21return (((n & 0xFF00) >> 8) | ((a & 0x00FF) << 8)); 22 }
3. 拓展應用
題目:不使用加減乘除四則運算實現兩個正整數相加。
解析:首先理解十進位制加法工作原理,主要分為三步,以4+9為例:1)相加相應位的值,不算進位,得3;2)計算進位值,得10,如果進位值為0則第一步得到的就是最終結果;3)把前兩步的結果相加,重複此過程得結果13。
再來看二進位制相加過程。1)相加相應位的值,不算進位,100 + 1001,得1101;2)計算進位值,得0000,如果進位為0則第一步得到的就是最終結果;3)把前兩步的結果相加,重複此過程的結果1101。
1 /*================================================================================================== 2* 相加相應位的值可按位異或,因為如果不考慮進位的和,只有0+1或者1+0才是1, 剛好符合異或的性質:0100 ^ 1001 = 1101 3* 計算進位可使用按位與,因為只有1+1才會發生進位並需要將這個進位左移1位: (0100 & 1001) << 1 = 0000 4* 然後一直迴圈直到進位為0,此時的結果就是輸入兩數之和了。 5*================================================================================================== 6*/ 7 int Add(int num1, int num2) { 8return num2 ? Add(num1 ^ num2, (num1 & num2)<<1) : num1;}
題目:給定一個非空整數陣列,其中有一個元素只出現一次,其它元素均出現兩次,請找出只出現一次的元素。(要求實現演算法具有線性時間複雜度,並且不實用額外空間)
示例:輸入[2, 2, 1],輸出1。輸入[3, 1, 2, 3, 1],輸出2。
解析:由於要求時間複雜度O(n),空間複雜度O(1),不能用排序,也不能使用map。考慮使用位操作運算求解。因為任何數與自身異或結果為0,任何數與0異或結果為其自身,將所有元素做異或運算,即a[1]⊕a[2]⊕...⊕a[n],那麼結果就是隻出現一次的元素,時間複雜度O(n)。過程如下圖:
題目:給定一個非空整數陣列,其中有兩個元素只出現一次,其它元素均出現兩次,請找出只出現一次的兩個元素。(要求實現演算法具有線性時間複雜度,而且只能開闢固定大小的記憶體空間,即與n無關)
示例:輸入[1, 2, 2, 1, 3, 4],輸出[3, 4]。
解析:根據前面找一個不同數的思路,如果這裡再把所有元素異或,得到的結果是隻出現一次的兩個元素異或得到的值。然後由於這兩個只出現一次的元素一定不相同,那麼這兩個元素的二進位制形式肯定至少有一位不同,即1個為0,另一個為1,先在需要找出這一位。根據異或的性質:任何數與自身異或結果為0,得到這個數字二進位制形式中任意一個為1的位都是我們要找的。之後以這一位是0還是1為標準,將陣列的n個元素分成兩部分。將這一位為0的所有元素異或得到的結果就是隻出現一次的兩個元素中的一個。將這一位為1的所有元素異或得到的結果就是隻出現一次的兩個元素中的另一個。如果忽略尋找不同位的過程,公遍歷陣列兩次,時間複雜度O(n)。過程如下圖:
Reference:
[1] https://www.cnblogs.com/zhoug2020/p/4978822.html
[2] https://blog.csdn.net/qq_16137569/article/details/82790378
[3] https://www.cnblogs.com/thrillerz/p/4530108.html
[4] https://www.cnblogs.com/fivestudy/p/10275446.html
[5] https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking