位運算總結
1.位運算符號
& \& &——按位與
如果兩個相應的二進制位都為1，則該位的結果值為1，否則為0
∣ | ∣——按位或
兩個相應的二進制位中只要有一個為1，該位的結果值為1
^——按位異或
若參加運算的兩個二進制位值相同則為0，否則為1
~——取反
用來對一個二進制數按位取反，即將0變1，1變0
舉例：
1000101 1000101 1000101 1000101& 0101100 | 0101110 ~ ^ 0101110——————————————————————————————————————————————————————————= 0000100 = 1101111 = 0111010 1101011
2.移位運算
< < << <<——左移
用來將一個數的各二進制位全部左移n位，低位以0補充，高位越界后舍棄。
1左移n位： 1 << n =2^n(這里指2的n次方)n左移1位： n << 1 =2*n
舉例：
short a=9115 0010001110011011 (9115的二進制表示)a << 1 =18230 0100011100110110 (注意高位越界后舍棄一個0，低位填充一個0)a << 2 = -29076 1000111001101100 (注意高位越界后舍棄兩個0，低位填充兩個0）
注意：左移是做乘2的運算，但這是在符號位（原碼將最高位符號以0表示正，1表示負eg:0010001110011011中的最高位0就是符號位，表示是整數；而1000111001101100最高位是1，表示是負數）不變的情況下。如果符號位發生了改變，說明已經不能做乘2的運算了，否則會溢出，得到的值不是乘2的結果。
注意：short是Java中的表示，它定義的也是整形，不過是16字節（這里為了闡述符號位的改變而使用）,而int是32字節
> > >> >>——右移
將一個數的各二進制位右移N位，移到右端的低位被舍棄，高位以符號位填充
n左移1位 ： n >> 1=|n/2.0| 算術右移等于除以2向下取整：（-3）>> 1 = -2 3 >> 1 = 1值得一提的是，“整數/2”在c++中實現為“除以2向零取整”，（-3）/ 2 = -1，3 / 2 = 1
舉例：
short b = 9115 0010001110011011 (9115 >> 1) = 4557 0001000111001101（注意低位越界后舍去了一個1，高位補一0） (9115 >> 2) = 2278 0000100011100110 (注意低位越界后舍去了兩個1，高位補兩0）short c=-32766(負數符號位為1) 1000000000000010-32766 >> 1 = -16383 1100000000000001(注意低位越界后舍棄一個0,高位補1)-32766 >> 2 = -8192 1110000000000000(注意低位越界后舍棄0和1,高位補倆1)
3.常用技巧
在m位二進制數中，通常稱最低為為第0位，從右到左依次類推，最高位為第m-1位
(n >> k) & 1 求n二進制下的第k位是0還是1，若結果為真，是1，若結果為假，是0。因為1的二進制數中只有第0位數是1，其余位數都是0。
n^=1,，即n=n^1,能讓n變成與原來相反的數（0或1）
n | (1 << k)，能把n的第k位變成1
a^b^b=a
x=x&(x-1)用于消去x的最后一位
4.運算符號優先級：
加減優先級最高，位或優先級最低，從左往右優先級遞減
加減 移位 比較大小 位與 異或 位或+，- <<,>> >,<,==,!= & ^ |
5.位運算常用技巧
<1> 判斷奇偶性
如果把 n 以二進制的形式展示的話，其實我們只需要判斷最后一個二進制位是 1 還是 0 就行了，如果是 1 的話，代表是奇數，如果是 0 則代表是偶數，所以采用位運算的方式的話，代碼如下：
if(n&1){ //若n&1==1(為真)//n是奇數
}
if(!(n&1)){ //若n&1!=1(為假)//n是偶數
}
<2> 求a的b次方
本題涉及數論數論數論，在次不詳細解釋，有興趣的話可以自己了解.
//快速冪
int pow(int a, int b) {int ans = 1;while (b != 0) {if ((b & 1) == 1) { // 添加括號，明確表達式優先級ans *= a;}a *= a;b = b >> 1;}return ans;
}
<3>找處未重復的數
數組中，只有一個數出現奇數次，剩下都出現偶數次，找出出現奇數次的。
思路：兩個相同的數異或的結果是 0，一個數和 0 異或的結果是它本身，所以我們把這一組整型全部異或一下。也就是說，那些出現了偶數次的數異或之后會變成0，那個出現奇數次的數，和 0 異或之后就等于它本身。
#include<iostream>
using namespace std;int main(){int a[9]={4,3,2,2,2,2,5,4,3};int ans=0;for(int i=0;i<9;i++){ans^=a[i];}cout<<ans;return 0;
}
<4> 用O(1)時間檢測整數n是否是2的冪次.
思路：
n如果是2的冪次，則：
1.n>0
2.n的二進制表示中只有一個1
一位n的二進制表示中只有一個1，所以使用n&(n-1)將唯一的一個1消去。
如果n是2的冪次，那么n&(n-1)得到結果為0，即可判斷。
eg: 8的二進制位1000，7的二進制位0111，8&7==0，所以8是2的冪次
#include<iostream>
using namespace std;int main(){int n;cin>>n;if(!(n&(n-1))) cout<<"YES";if(n&(n-1)) cout<<"NO";return 0;
}
