在上篇C/C++位運(yùn)算概述與應(yīng)用（一）

講了位運(yùn)算的概述，要明白位運(yùn)算是在二進(jìn)制中的運(yùn)算方式，所有其他進(jìn)制的數(shù)在進(jìn)行位運(yùn)算時(shí)都要先轉(zhuǎn)化成二進(jìn)制數(shù)再進(jìn)行運(yùn)算。所以，位運(yùn)算是一種十分高效的運(yùn)算，無論是嵌入式編程還是優(yōu)化系統(tǒng)的核心代碼，適當(dāng)?shù)倪\(yùn)用位運(yùn)算總是一種迷人的手段。如果能把位運(yùn)算運(yùn)用的神出鬼沒，很多程序都將十分精妙。
那么今天我們就來看看位運(yùn)算能進(jìn)行哪些應(yīng)用吧。

1.判斷某個(gè)數(shù)的奇偶

相信大多數(shù)人第一思維就是

if (n % 2 == 1)
    cout << "odd" << endl;
else
    cout << "even" << endl;

這么寫，對(duì)！當(dāng)然對(duì)，沒有人說你錯(cuò)，但是，我們竟然掌握了位運(yùn)算，為什么不用時(shí)間效率更加高效的方法呢？

if (n & 2)
    cout << "odd" << endl;
else
    cout << "even" << endl;

哪種高效，自己可以去試試咯

2.m的n次方

第一反應(yīng)，pow（)，嘿嘿，當(dāng)然也對(duì)，如果不讓你用這個(gè)函數(shù)呢？
累乘唄！ 我想，不只是你，小學(xué)生都知道，時(shí)間復(fù)雜度為O（n）。
來吧，來個(gè)更高效的位運(yùn)算大法：時(shí)間復(fù)雜度近為 O(logn)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    //求3的11次
    int m = 3,n=11;  //11的二進(jìn)制為 1011
    //m^11 = m^1000 * m^0010 * m^0001;
    int sum = 1;
    while (n != 0) 
    {
        if (n & 1 == 1) //判斷最后一位是不是1 是的話就乘以
            sum *= m;
        m *= m;
        n = n >> 1; //右移一位
    }
    cout << sum << endl;
    return 0;
}

3.交換兩個(gè)數(shù)（不借助第三個(gè)變量）

不借助第三個(gè)變量！
a=a+b; b=a-b; a=a-b；
嘿嘿 當(dāng)然，這種也行，來看咱們的位運(yùn)算大法吧：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    while (cin >> a >> b)
    {
        a ^= b ^= a ^= b;
        cout << a << " " << b;
    }
    return 0;
}

看不懂？ 沒事 看下面這個(gè)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;//a = 3 = 0011  b = 4 = 0100
    while (cin >> a >> b)
    {
        a = a ^ b; //a = 0011 ^ 0100 = 0111
        b = a ^ b; //b = 0111 ^ 0100 = 0011
        a = a ^ b; //a = 0111 ^ 0011 = 0100
        cout << a << " " << b;
    }
    return 0;
}

嘿嘿是不是很有逼格

4.獲得int型最大值

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a = (1 << 31) - 1;//或者~(1 << 31)
    cout << a;//2147483647
    return 0;
}

5.獲得int的最小值

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a = 1 << 31;
    cout << a;//-2147483648
    return 0;
}

6.乘/除2的值

n<<1;//n乘2
n>>1;//n除2

7.判斷兩個(gè)數(shù)正負(fù)性是否相同

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,y;
    while (cin >> x >> y)
    {
        if ((x ^ y) >= 0)
            cout << "identical" << endl;
        else
            cout << "inequality" << endl;
    }
    return 0;
}

8.判斷是否為2的整數(shù)冪

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a = 64 & 63;// 01000000 & 00111111 = 0   64是2的整數(shù)冪
    int b = 8 & 7;// 1000 & 0111 = 0     8是2的整數(shù)冪
    int c = 7 & 6;// 0111 & 0110 = 6     7不是2的整數(shù)冪
    int n;
    cin >> n;
    if (n & (n - 1))
        cout << "NO\n";
    else
        cout << "Yes\n";
}

9.找出不大于n的最大的2的整數(shù)冪

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin >> n)
    {
        for (int i = n;i >= 0;i--)
        {
            if (!(i & (i - 1)))
            {
                cout << i << endl;
                break;
            }
        }
    }
}

10.除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

只要讓數(shù)組中的元素依次相“異或”，出現(xiàn)兩次的元素最終異或?yàn)?，僅剩下唯一只出現(xiàn)過一次的元素。
比如
樣例輸入
5
4 2 3 2 4
輸出 3

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, a[100],q;
    while (cin >> n)
    {
        q = 0;
        for (int i = 0;i < n;i++)
        {
            cin >> a[i];
            q ^= a[i];
        }
        cout << q << endl;
    }
    return 0;
}