這里寫目錄標題

• • • • 一、常(裝)見(逼)的位操作
      • • 先看幾個有意思的位操作：
        • 1、判斷奇數(shù)偶數(shù)
        • 2、交換兩個數(shù)字
        • 3、找出沒有重復的數(shù)字
        • 4、m的n次方
        • 5、判斷一個數(shù)是不是二的指數(shù)
        • 6、找出不大于N的最大2的冪指數(shù)
      • 二、leetcode解題
      • • 136.只出現(xiàn)一次的數(shù)字(簡單)
        • 191.位1的個數(shù)(簡單)

看完本文，可以順便解決leetcode以下兩個題目：
136.只出現(xiàn)一次的數(shù)字(簡單)
191.位1的個數(shù)(簡單)

一、常(裝)見(逼)的位操作

先看幾個有意思的位操作：

或操作 | 和空格將英文字符轉換為小寫，小寫本身還是小寫

(‘a(chǎn)’ | ’ ') = ‘a(chǎn)’
(‘A’ | ’ ') = ‘a(chǎn)’

與操作 & 和下劃線將英文字符轉換為大寫，大寫本身還是大寫

(‘b’ & ‘’) = ‘B’
(‘B’ & '’) = ‘B’

n&(n-1) 消除數(shù)字 n 的二進制表示中的最后一個 1

異或^和空格進行英文字符大小寫互換;判斷異號

(‘d’ ^ ’ ') = ‘D’
(‘D’ ^ ’ ') = ‘d’
x^y < 0;異號，否則同號

下面我們從簡單開始，一步一步的實現(xiàn)復雜的位運算~

1、判斷奇數(shù)偶數(shù)

看到這個，你肯定覺得很簡單，然后隨手寫下：

if (n % 2 == 0) { // 偶數(shù) } else { // 奇數(shù) }

其實使用位運算，可以這樣寫

if ( n & 1 == 1) {// 奇數(shù) } else {// 偶數(shù) }

因為如果一個二進制表示偶數(shù)的話

偶數(shù)的最后一位肯定是0；

奇數(shù)的最后一位肯定是1；

2、交換兩個數(shù)字

這個也是很常見的操作，很簡單的就可以寫下來：

temp = x; x = y; y = temp;

但是如果在實際工作中，遇到不借助輔助空間，依舊讓你去交換兩個數(shù)字呢？
這個時候，位運算的優(yōu)勢就體現(xiàn)出來了
位運算實現(xiàn)如下：

x = x^y y = x^y x = x^y

看的第一眼，肯定很懵~ 啥玩意兒這是

首先，我們需要知道兩個個基礎的公式：

n^n =0; 即相同的兩個數(shù)異或結果是0
n^0 = n;一個數(shù)和0異或的結果是本身

所以，上面展開一下，就是

x = x^y y = x^y^y = x^0 = x x = x^y = x^y^x = x^x^y = 0^y = y

3、找出沒有重復的數(shù)字

我們以上面的為基礎，即相同的兩個數(shù)異或結果是0；一個數(shù)和0異或的結果是本身
那我們就把這一些數(shù)字，遍歷一遍，全部異或一下，不就OK了？

4、m的n次方

要求一個數(shù)m的n次方，但是不能使用POW函數(shù)，如何做？
不要使用 m x m x m x m x m~ 一直乘以n次，太low了；
時間復雜度就是 O(n)

使用階乘，復雜度可以降低到O(log N)

int pow(int n){int sum = 1;int tmp = m;while(n != 0){if(n & 1 == 1){sum *= tmp;}tmp *= tmp;n = n >> 1;}return sum; }

上述代碼要是不理解二進制可能你就看不懂，這里我來舉例解釋一下

比如，求m的 5次方
我們把5用二進制表示，就是 0101，
從右往左看，第一個1 代表一個m
第二個1代表一個m x m x m x m ;
當二進制的這一位有1的時候，才把該位置代表的累乘的數(shù)算上，否則不算，繼續(xù)看下一位的情況；

5、判斷一個數(shù)是不是二的指數(shù)

如果一個數(shù)，是二的指數(shù)，那么它的二進制表示，肯定只有一個1
結合上面說到的：n&(n-1) 消除數(shù)字 n 的二進制表示中的最后一個 1

問題就好解決了

return (n > 0 ) && (n & (n - 1) == 0) ) ;

6、找出不大于N的最大2的冪指數(shù)

假設這個數(shù)是 19；
19用二進制表示就是 00010011
我們需要的結果就是 16 ；00010000
也就是 把 0010011，只保留最左邊的一個1；
這個思路很簡單，就是把最左邊的1后面位，全部變成1；然后整體加1；由于加1之后會進位，所以在整體右移一位

應該怎么最左邊的1后面位，全部變成1呢？

n |= n >> 1;
n |= n >> 2;
n |= n >> 4;

n |= n >> 1;
結果是最左邊的1和其右邊，也會有一個1；11

n |= n >> 2;
結果是最左邊的11和其右邊，也會有一個11；1111

n |= n >> 4;
結果是最左邊的1111和其右邊，也會有一個11；11111111

如此這樣，后面就都變成1了，然后+1，右移一位就行

二、leetcode解題

136.只出現(xiàn)一次的數(shù)字(簡單)

這個題剛剛上面說過了，全部都異或
直接上答案；

class Solution { public:int singleNumber(vector<int>& nums) {//異或int n=nums.size();int res=0;for(int i=0;i<n;i++){res^=nums[i];}return res;} };

191.位1的個數(shù)(簡單)

思路：
只需要記得：
n&(n-1) 消除數(shù)字 n 的二進制表示中的最后一個 1

class Solution { public:int hammingWeight(uint32_t n) {int res = 0;while (n != 0) {n = n & (n - 1);res++;} return res;} };

總結

以上是生活随笔為你收集整理的位运算的那些奇技淫巧 | 掌(装)握(逼)必备，妙解两道算法题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。