位運算的常見操作和題目 · 點滴算法

# 一、位運算基本操作 <table border="1" cellspacing="0" cellpadding="0" style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px"><tbody><tr><td valign="top">& ? ? ? ?</td><td valign="top">?與 ? ? ? ? ??</td><td valign="top">1 & 1 = 1；1 & 0 = 0；0 & 0 = 0 ?只有當兩個位都為1時，結果為1</td></tr><tr><td valign="top">|??</td><td valign="top">?或????</td><td valign="top">1 | 1 = 1；1 | 0 = 1；0 | 0 = 0 ? 只有兩個位都為0時，結果為0</td></tr><tr><td valign="top">^????</td><td valign="top">異或</td><td valign="top">1 ^ 1 = 0；1 ^ 0 = 1；0 ^ 0 = 0 ? 兩個位相同時為0，相異時為1</td></tr><tr><td valign="top">~???</td><td valign="top">取反</td><td valign="top">0變1，1變0</td></tr><tr><td valign="top"><<?</td><td valign="top">左移</td><td valign="top">各二進位全部左移若干位，高位丟棄，低位補0</td></tr><tr><td valign="top">>>?</td><td valign="top">右移</td><td valign="top">二進位全部右移若干位，對無符號數，高位補0；有符號數，各編譯器處理方法不一樣，有的補符號位（算術右移），有的補0（邏輯右移）</td></tr></tbody></table> 1、以上運算符，僅~是單目運算符，其他都是雙目運算符。 2、位操作僅針對整型數據，對float、double進行位操作會出錯。 3、VS2010 和GCC均采用算術右移：對負數右移，會在其高位補符號位，也就是補1。 4、還有其他復合位操作： &= ? ? ?|= ? ? ?<<= ? ? >>= # 二、位操作的運用 ### 1、奇偶性的判斷對于二進制表示來說，其最右位為1則該數為奇數，最右位為0則該數為偶數。 ~~~ int a; cin >> a; if (a & 1) cout << "奇數" << endl; if ((a & 1) == 0) //注意：&的優先級低于==的優先級，因此if內部與運算必須加括號！ cout << "偶數" << endl; ~~~ ### 2、不借助變量交換兩個數具體查看文章：[不借助變量交換兩個數](http://blog.csdn.net/u013074465/article/details/44342629) ### 3、取相反數也就是將正數n變為-n，將負數n變為-n。將整數取反加1即可得到其相反數： ? ? ? ? ? 例如，32位系統中正數13（二進制表示為00000000 00000000 00000000 00001101）， ? ? ? ? 取反為（11111111 11111111?11111111 11110010）， ? ? ? ? ? 然后再加1為（11111111?11111111 ?11111111 11110011），計算機中數是用二進制的補碼表示的， ? ? ? ? ? 因此取反加1的結果（11111111?11111111 ?11111111 ?11110011）即為-13的二進制補碼表示形式。常見的一個等式：-n = ~(n - 1) = ~n + 1 例子：求某整數的絕對值： ~~~ //求某整數的絕對值 int my_abs(int number) { if (number < 0) { return ~number + 1; //或return -number; 或return ~(n - 1) } return number; } ~~~ ### 4、整數二進制表示中最右邊的1 獲取整數二進制表示中最右側的1：n & (-n) ?等價于 n & ~(n - 1) 。 ? ? ? 例如，n = 1100， -n = 0100，那么n & (-n) = 0100，這樣就獲取到了二進制表示中最右側的1。去除整數二進制表示中最右側的1：n & (n - 1) ? ? ? 例如，n = 1100，n - 1 = 1011，那么n & (n - 1) = 1000，這樣就去除了二進制表示中最右側的1。在文章[位操作實現加減乘除四則運算](http://blog.csdn.net/u013074465/article/details/42680239#t3)中的乘法操作就用到了本小結提到的這兩個技巧。 ### 5、32位系統某數右移/左移32位或更多位 ? ? ?在移位運算時，byte、short和char類型移位后的結果會變成int類型，對于byte、short、char和int進行移位時，規定實際移動的次數是移動次數和32的余數，也就是移位33次和移位1次得到的結果相同。參考文章：[位移操作的另類情況](http://blog.csdn.net/u013074465/article/details/44645817) # 三、位運算相關的題目 ### 1、二進制中1的個數用到了n & (n - 1) (1)方法一：參考文章：[整數的二進制表示中1的個數](http://blog.csdn.net/u013074465/article/details/42617293) ? ? 方法二：[二進制位的翻轉和二進制表示中1的個數](http://blog.csdn.net/u013074465/article/details/45485959) (2) 輸入兩個數A和B，輸出將A轉換為B所需改變的二進制的位數。方法：首先，A異或B得到的是A和B中不相同位數組成的數，然后再求這個數二進制表示中1的個數，即為所求。 ### 2、數組中只出現一次的數字用到了n & (n - 1) 數組中僅出現一次的一個數字、僅出現一次的兩個數字參考文章：[http://zhedahht.blog.163.com/blog/static/2541117420071128950682/](http://zhedahht.blog.163.com/blog/static/2541117420071128950682/) ?? 數組中僅出現一次的三個數字參考文章：[http://zhedahht.blog.163.com/blog/static/25411174201283084246412/](http://zhedahht.blog.163.com/blog/static/25411174201283084246412/)?? ### 3、不用加減乘除做加法參考文章：[http://zhedahht.blog.163.com/blog/static/254111742011125100605/](http://zhedahht.blog.163.com/blog/static/254111742011125100605/) ? ### 4、位操作實現加減乘除運算 [位操作實現加減乘除四則運算](http://blog.csdn.net/u013074465/article/details/42680239) ### 5、不借助變量交換兩個數參考文章：[不借助變量交換兩個數](http://blog.csdn.net/u013074465/article/details/44342629) ### 6、比較兩個數大小參考文章：[不借助if、switch等語句求兩個數較大的一個](http://blog.csdn.net/u013074465/article/details/42684559) ### 7、二進制位的翻轉 [字符串合并處理（二進制位的倒序）](http://blog.csdn.net/u013074465/article/details/45485515) [二進制位的翻轉](http://blog.csdn.net/u013074465/article/details/45485959) ### 8、二進制表示的高低位交換 [http://blog.csdn.net/morewindows/article/details/7354571](http://blog.csdn.net/morewindows/article/details/7354571) ### 9、位操作與空間壓縮 [http://blog.csdn.net/morewindows/article/details/7354571#t6](http://blog.csdn.net/morewindows/article/details/7354571#t6) ### 10、bitmap對海量數據排序 [bitmap對海量無重復的整數排序](http://blog.csdn.net/u013074465/article/details/46956295) ### 11、求兩個數中較小的那個 y ^ ((x ^ y) & -(x < y)) 分析：當x < y時，-(x < y)為-1，其補碼形式全為1，則(x ^ y) & -(x < y) = x ^ y，則上述表達式返回的是較小的數x；當x >= y時，-(x < y)為0，補碼形式為全0，則(x ^ y) & -(x < y) = 0，則表達式返回的是較小的數y。