（在計算機中,數(shù)都是二進制來存儲的,所以二進制的一些運算要比普通的等價運算(+,-,*,/)更快,更簡單,所以知道他們的技巧顯得尤其重要!）
異或運算：
首先 異或(^) 表示當兩個數(shù)的二進制表示废麻，進行異或運算時，當前位的兩個二進制表示不同則為 1 相同則為 0 .該方法被廣泛推廣用來統(tǒng)計一個數(shù)的1的位數(shù)矩屁！
所以二進制中 對應二進制位數(shù)進行異或操作時, 與0異或?qū)摱M制位數(shù)值不變, 與 1 異或時對應該二進制位數(shù)值相反(即 1 變成 0 , 0 變成 1).
參與運算的兩個值遍膜，如果兩個二進制相應位相同，則結(jié)果為0扛或，否則（不同）為1绵咱。
即：
0^0 = 0，
1^0 = 1熙兔，
0^1 = 1悲伶，
1^1 = 0
按位異或的3個特點:
(1) 00=0,01=1 0異或任何數(shù)＝任何數(shù) (這里的任何數(shù)是指二進制位上的那個數(shù),即任何數(shù)要么為0 ，要么為1 .)
(2) 10=1,11=0 1異或任何數(shù)－任何數(shù)取反 (同理)
(3) 任何數(shù)異或自己＝把自己置0
按位異或的幾個常見用途:
(1) 使某些特定的位翻轉(zhuǎn)
例如對數(shù)10100001的第2位和第3位翻轉(zhuǎn)(不管是0 還是 1 都可以,因為上面也說了 任何數(shù)與1 異或 任何數(shù)取反 ! 所以可以進行翻轉(zhuǎn)!)住涉，則可以將該數(shù)與00000110進行按位異或運算
10100001^00000110 = 10100111
(2) 實現(xiàn)兩個值的交換麸锉，而不必使用臨時變量。
例如交換兩個整數(shù)a=10100001舆声，b=00000110的值花沉，可通過下列語句實現(xiàn)：
a = a^b； //a=10100111
b = b^a媳握； //b=10100001
a = a^b碱屁； //a=00000110
(一句話: a=ab(b=a) ; )
再次 & (與) 二進制對應位上都是 1 結(jié)果才是1 . 否則就是 0 . （和電路開關很像,串聯(lián),同時開才開,否則就是關.）
技巧 1 : 把一個整數(shù)減去1,再和原整數(shù)做與運算,會把該整數(shù)的二進制中的最右邊一個1變成0 , 那么一個整數(shù)的二進制表示中有多少個1,就可以進行多少次這樣的操作.
技巧 2 : 二進制的最低位是1就是奇數(shù),是0就是偶數(shù).
(原因 : 二進制的位數(shù)（由低到高）分別代表著1,2,4,8,16,32,64,128,256,512,1024.只有最低位的這個是1或0,所以二進制最低位為1時,就是奇數(shù)(偶數(shù)由上面的這些基本的組成嘛!) )
技巧 3 ：算一個數(shù)的二進制最低位是多少, 直接 x&1 = x的最低位是多少.
例 1： 如何用一條語句表示判斷一個整數(shù)是不是2的整數(shù)次方.
解 ： 因為是整數(shù)次方,所以該數(shù)的二進制中必定只含一個 1 . 所以結(jié)合上面的技巧,就有 !(x & (x-1) ) ;
例 2 : 寫一個函數(shù),判斷一個數(shù)的二進制中多少個 1 .
int check(int x)
{
int num=0;
while(x)
{
x &= (x-1);
num++;
}
return num;
}
例 3 : 輸入兩個整數(shù)m和n，計算需要改變m的二進制表示中的多少位才能得到n .
思路: 結(jié)合異或的性質(zhì)運算,首先讓 m^n 得到一個數(shù),則這個數(shù)二進制中有多少個1 , 則m,n就有多少位不同.所以統(tǒng)計得到的這個數(shù)中又多少個1就行了.
int check(int m,int n)
{
int x=m^n;
int num=0;
while(x)
{
x &= (x-1);
num++;
}
return num;
}
例 4：判斷一個數(shù)的奇偶性(結(jié)合技巧)
if(x&1)
是奇數(shù).
else
是偶數(shù).
例 5 ：算一個數(shù)二進制的補位數(shù)(比如說5的二進制是101, 所以補位數(shù)就是010, 即2,當然不能直接用~)
int sum=0,s=1;
while(t){
int m=((t&1)^1);
sum += s*m; //是1才算值, 是零就不管.
t >>= 1; //不斷除二.
s <<= 1; //s表示2的幾次方.
}
二進制的一些操作:
1：將一個十進制的數(shù)分解為二進制表示.
while(t){
int m=t&1;
a[k++]=m;
t >>= 1;
}
2：將一個十進制數(shù)轉(zhuǎn)化成二進制的同時再算出轉(zhuǎn)化后的這個數(shù)十進制表示為多少.
int s=1,sum=0;
while(t){
int m=t&1;
sum += s*m;
s <<= 1;
t >>= 1;
}
3：取某個數(shù)的第 i 個 二進制位數(shù).
int Getbit(int x,int i)
{
return (x >> i) & 1;
}
4：把 x 的第 i 位設置成 v .
void setbit(int & x,int i,int v) //這樣引用的話,形參改變對應實參也會改變.
{
if(v ){
c |= (1 << i);
}
else
c &= ~(1 << i);
}
5：把x的第 i 位翻轉(zhuǎn).(1 翻為0 , 0 翻為 1).
void flipbit(char & c ,int i)
{
c ^= (1 << i) ;
}
一大波操作 :
去掉最后一位 |(101101->10110) | x >> 1
在最后加一個0 |(101101->1011010) | x < < 1
在最后加一個1 |(101101->1011011) | x < < 1+1
把最后一位變成1 |(101100->101101) | x | 1
把最后一位變成0 |(101101->101100) | x | 1-1
最后一位取反 |(101101->101100) | x ^ 1
把右數(shù)第k位變成1 | (101001->101101,k=3) | x | (1 < < (k-1)) //k>=1, 即第一位算的是1
把右數(shù)第k位變成0 | (101101->101001,k=3) | x & ~ (1 < < (k-1))
右數(shù)第k位取反 | (101001->101101,k=3) | x ^ (1 < < (k-1))
取末三位 | (1101101->101) | x & 7
取末k位 | (1101101->1101,k=5) | x & ((1 < < k)-1)
取右數(shù)第k位 | (1101101->1,k=4) | x >> (k-1) & 1
把末k位變成1 | (101001->101111,k=4) | x | (1 < < k-1)
末k位取反 | (101001->100110,k=4) | x ^ (1 < < k-1)
把右邊連續(xù)的1變成0 | (100101111->100100000) | x & (x+1)
把右起第一個0變成1 | (100101111->100111111) | x | (x+1)
把右邊連續(xù)的0變成1 | (11011000->11011111) | x | (x-1)
取右邊連續(xù)的1 | (100101111->1111) | (x ^ (x+1)) >> 1
去掉右起第一個1的左邊 | (100101000->1000) | x & (x ^ (x-1))
判斷奇數(shù) (x&1)==1
判斷偶數(shù) (x&1)==0
取右邊第一個1所在位置 x&-x
將右邊第一個1變?yōu)?. x &= (x-1)
移位運算要點
1: 它們都是雙目運算符蛾找，兩個運算分量都是整形娩脾，結(jié)果也是整形。
2: "<<" 左移：右邊空出的位上補0腋粥，左邊的位將從字頭擠掉晦雨，其值相當于乘2。
3: ">>"右移：右邊的位被擠掉隘冲。對于左邊移出的空位闹瞧，如果是正數(shù)則空位補0，若為負數(shù)展辞，可能補0或補1奥邮，這取決于所用的計算機系統(tǒng)。
4: ">>>"運算符罗珍，右邊的位被擠掉洽腺，對于左邊移出的空位一概補上0。
位運算符的應用 (源操作數(shù)s 掩碼mask)
(1) 按位與-- &
1: 清零特定位 (mask中特定位置0覆旱，其它位為1蘸朋，s=s&mask)
2: 取某數(shù)中指定位 (mask中特定位置1，其它位為0扣唱，s=s&mask)
(2) 按位或-- |
常用來將源操作數(shù)某些位置置為1藕坯，其它位不變团南。 (mask中特定位置1，其它位為0 s=s|mask)
(3) 位異或-- ^1
1: 使特定位的值取反 (mask中特定位置1炼彪，其它位為0 s=s^mask)
2: 不引入第三變量吐根，交換兩個變量的值(a = a^b^(b==a); || a ^= b; b ^= a; a ^= b;)
二進制補碼運算公式：(不懂負數(shù)的點擊最下方)
-x = ~x + 1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
比較應用舉例
(1)整數(shù)的平均值對于兩個整數(shù)x,y，如果用 (x+y)/2 求平均值辐马，會產(chǎn)生溢出拷橘，因為 x+y 可能會大于INT_MAX，
但是我們知道它們的平均值是肯定不會溢出的喜爷，我們用如下
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}
(2) x 的 相反數(shù) 表示為 (~x+1)
