第三節(jié)　位運(yùn)算

基礎(chǔ)知識(shí)

程序中的所有數(shù)在計(jì)算機(jī)內(nèi)存中都是以二進(jìn)制的形式存儲(chǔ)的，位運(yùn)算就是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作（補(bǔ)碼且符號(hào)位也參與運(yùn)算，有關(guān)補(bǔ)碼的知識(shí)見第二章的第二節(jié)），位運(yùn)算符及其運(yùn)算規(guī)則如下。

按位與（&）

兩個(gè)都是1才是1。例如：

---

00101        5
11100        28
& ---------------
00100        4

---

&運(yùn)算通常用于二進(jìn)制數(shù)的取位操作，例如一個(gè)數(shù)“& 1”的結(jié)果就是取二進(jìn)制數(shù)的最末位。這可以用來判斷一個(gè)整數(shù)的奇偶性，二進(jìn)制的最末位為0表示該數(shù)為偶數(shù)，最末位為1表示該數(shù)為奇數(shù)。對(duì)于一個(gè)數(shù)a，a=a & (a-1)的作用是將a的二進(jìn)制數(shù)最右邊的1變?yōu)?。

按位或（|）

只要有一個(gè)為1就為1。例如：

---

00101        5
11100        28
| ---------------
11101        29

---

|運(yùn)算通常用于二進(jìn)制數(shù)特定位上的無條件賦值，例如一個(gè)數(shù)“| 1”的結(jié)果就是把二進(jìn)制數(shù)最末位強(qiáng)行變成1。如果需要把二進(jìn)制數(shù)最末位變成0，對(duì)這個(gè)數(shù)“| 1”之后再減1就可以了，其實(shí)際意義就是把這個(gè)數(shù)強(qiáng)行變成最接近的偶數(shù)。

按位異或（^）

相同為0，不同為1（或理解為“半加”，也就是不進(jìn)位的二進(jìn)制數(shù)加法）。例如：

---

00101        5
11100        28
^ ---------------
11001        25

---

^運(yùn)算可以用于簡(jiǎn)單的加密，比如我想告訴朋友我的QQ密碼是123456，但又怕別人知道，所以我和朋友約定用19491001作為密鑰，123456^19491001=19434233，我就把19434233告訴朋友，然后朋友再計(jì)算19434233^19491001=123456，就得到我的QQ密碼了。

在密碼學(xué)中，上述過程的123456稱為明文，19434233稱為密文，19491001稱為密鑰，明文經(jīng)過加密過程轉(zhuǎn)變?yōu)槊芪牟鬏斀o目標(biāo)對(duì)象，目標(biāo)對(duì)象接收后將密文經(jīng)過解密過程轉(zhuǎn)變?yōu)槊魑模绱吮憧蓪?shí)現(xiàn)安全的傳輸，即便被別人截獲了傳輸?shù)拿芪模瑳]有密鑰也無法得知明文。

加法的逆運(yùn)算是減法，乘法的逆運(yùn)算是除法，^運(yùn)算的逆運(yùn)算是它本身。由此可寫出一個(gè)不需要中間變量的swap過程。

---

int a = 10,b = 5;
// 原交換方法
int t = a;
a = b;
b = t;
// 借助互逆運(yùn)算
a = a + b;
b = a - b;
a = a - b;
// 借助^
a = a ^ b;
b = a ^ b;
a = a ^ b;

---

注意：^的交換方法不能用于一個(gè)數(shù)的自我交換，會(huì)導(dǎo)致數(shù)據(jù)變?yōu)?。

按位取反（~）

單目運(yùn)算符，1變成0，0變成1，例如：

---

00101        5
~ ---------------
11010        -6

---

注意：11010為補(bǔ)碼。

使用~運(yùn)算時(shí)要格外小心，需要注意整數(shù)類型有沒有符號(hào)。如果~的對(duì)象是無符號(hào)整數(shù)（unsigned），那么得到的值就是它與該類型上界的差。

左移（<<）

a<<b就表示把a(bǔ)轉(zhuǎn)為二進(jìn)制后左移b位（在后面添加b個(gè)0）。例如100的二進(jìn)制數(shù)為1100100，而110010000轉(zhuǎn)成十進(jìn)制數(shù)是400，那么100<<2=400。可以看出，a<<b的值實(shí)際上就是a乘以2的b次方，因?yàn)樵诙M(jìn)制數(shù)后添加一個(gè)0就相當(dāng)于該數(shù)乘以2。

通常認(rèn)為a<<1比a*2更快，因?yàn)榍罢呤歉讓右恍┑牟僮鳌Ｒ虼顺绦蛑谐艘?的操作請(qǐng)盡量用左移一位來代替。

定義一些常量可能會(huì)用到<<運(yùn)算。你可以方便地用1<<16-1來表示65535。很多算法和數(shù)據(jù)結(jié)構(gòu)要求數(shù)據(jù)規(guī)模必須是2的冪，此時(shí)可以用<<來定義Max_N等常量。

右移（>>）

與<<相似，a>>b表示把a(bǔ)轉(zhuǎn)為二進(jìn)制數(shù)后右移b位，低位舍棄b位，高位補(bǔ)b位符號(hào)位（正數(shù)補(bǔ)0、負(fù)數(shù)補(bǔ)1）。

右移運(yùn)算對(duì)于正數(shù)，相當(dāng)于a除以2的b次方（取商），想辦法用>>代替除法運(yùn)算可以使程序效率大大提高。

在其他編程語言（如Java）中，右移運(yùn)算符分為帶符號(hào)（>>）和無符號(hào)（>>>）兩種。二者的區(qū)別在于舍棄低位后高位所補(bǔ)的數(shù)字，若帶符號(hào)，則補(bǔ)符號(hào)位（正0負(fù)1）；若無符號(hào)，則固定補(bǔ)0。

位運(yùn)算符優(yōu)先級(jí)

速記：從高到低，反、移、與、異、或，四則運(yùn)算在反、移之間。

賽題訓(xùn)練

1.二進(jìn)制數(shù)11101110010111和01011011101011進(jìn)行邏輯或運(yùn)算的結(jié)果是（　）。

A. 11111111011111

B. 11111111111101

C. 10111111111111

D. 11111111111111

2.二進(jìn)制數(shù)11101110010111和01011011101011進(jìn)行邏輯與運(yùn)算的結(jié)果是（　）。

A. 01001010001011

B. 01001010010011

C. 01001010000001

D. 01001010000011

3.為了統(tǒng)計(jì)一個(gè)非負(fù)整數(shù)的二進(jìn)制形式中1的個(gè)數(shù)，代碼如下：

---

int CountBit(int x)
{
    int ret = 0;
    while (x)
    {
        ret++;
        ___________;
    }
    return ret;
}

---

則空格內(nèi)要填入的語句是（　）。

A. x>>=1

B. x &=x-1

C. x |=x>>1

D. x<<=1

4.二進(jìn)制數(shù)00101100和01010101異或的結(jié)果是（　）。

A. 00101000

B. 01111001

C. 01000100

D. 00111000