藍橋杯 第07期

「一切的一切，都歸結於0和1。」

恭喜你看到這裡，從本期起，我們將更上一層樓。

01

—

Why?

為什麼會存在位運算這麼一個平時幾乎用不到的工具？它的意義是什麼？

我們都知道，計算機運行的本質是數字電路對高低電平（0和1）進行與、或、非運算。在計算機的世界裡，我們的所見、所聞、所知都離不開二進位。此話何解？首先我們先稍稍介紹一下數字邏輯電路。

利用異或門和與門，設計一個半加器（一種二輸入加法器）。

輸入：

A, B信號源；

輸出：

X, P，其中X為低位，P為高位。

首先我們來看看，對於這個加法器，它的真值表是什麼？

那麼異或門(XOR Gate)的真值表是什麼呢？

接下來我們可以看到的是，對於低位X來說，它的真值表和異或門的真值表相同，而對於高位P來說，它的真值表和與門(AND Gate)表現相同！所以我們可以很容易設計出它的邏輯電路圖：

這樣我們就成功設計了一個能將兩個單比特數值相加的加法器。當然計算機設計肯定不會這麼簡單，實際上加法器應該使用全加器，這裡就不展開了。

而在編程語言中，最符合這種計算模式的操作就是位運算！比如我們需要判斷一個IP地址是哪類的地址，對於給定的IP地址（事實上它就是32個比特，這裡用16進位來表示，以縮短長度）：0x6E8BFC4A（對應點分十進位：110.139.252.74）來說。我們規定它的類型如下：

A類地址：首個比特為0；

B類地址：首個比特為1，且第二個比特為0；

C類地址：首個比特和第二個比特均為1，且第三個比特為0

接下來我們就運用這一規則對IP地址進行判斷：

longIPAddress;

charIPType;

inti = 0;

while( (IPAddress

i++;

switch( i )

{

case0: IPType = "A";break;

case1: IPType = "B";break;

case2: IPType = "C";break;

}

請大家自行模擬一遍運行過程。『

值得一提的是，上文中的0x80000000我們通常稱之為掩碼(mask)。大家應該聽說過子網掩碼（subnet mask），子網掩碼是這麼使用的：

unsigned longIP_address;

// 這裡假設子網掩碼是 255.255.0.0

unsignedlongsubnet_mask =0xFFFF0000;

unsignedlonghost_number;

unsignedlongnetwork_number;

// 利用IP地址和子網掩碼計算網路號

host_number = IP_address & subnet_mask;

// 利用IP地址和子網掩碼計算主機號，將子網掩碼翻轉（按位取非）獲得用於計算網路號的掩碼

network_number = IP_address & (~subnet_mask);

這就是位運算最常見的應用場景，當然它對於演算法來說也是必不可少的，比如用於快速冪運算，以後再介紹它了。本文今後都會使用16進位數來表示掩碼，因為一個16進位位剛好對應4個二進位位，非常方便。

工具推薦：開始 -> 計算器 -> 程序員 (僅Windows10)

02

—

使用示例

本文接下來將結合實例來介紹各種位運算運算符的使用方法，請多思考，多計算，拿出紙和筆。

例一：(超大隨機數生成) 請生成一個unsigned long long類型的隨機數，要求這個 隨機數對於範圍內的整數都是均勻分布的。

我們一般如何生成服從均勻分布的隨機數呢？像這樣：

// 初始化隨機數種子

srand( time(NULL) );

rand();

利用標準庫中的rand()函數我們可以生成出隨機數，但是rand()函數僅生成範圍為0-32767的無符號int型隨機數。有的時候我們可能希望生成更大的隨機數，怎麼辦？

可能的方案：倍增（注意，這個方法是不對的，下面說明）

// 假設我們要生成 0 - 65534(2*32768) 範圍內的均勻整隨機數，如何做？

srand( time(NULL) );

/* 1 */

intrandN1 = 2 * rand();

/* 2 */

intrandN2 = rand() + rand();

請做實驗，判斷1和2哪個是正確的？

答案是，它們都不正確。對於randN1，它一定是一個偶數，顯然並不符合服從均勻分布的要求，從而產生隨機數生成的 「鋸齒」 現象；而對於randN2，它對0 - 65534之間不同的整數值的取值概率不同。

那該怎麼辦？或許我們可以從位運算中找到答案。計算機里的整數可以由一個二進位序列表示。如果我們隨機生成其中的每一個比特，那麼我們就可以生成一個隨機的整數。

觀察rand()函數生成的數的範圍：0-32767 ，寫成2進位就是：0x0000 - 0x7FFF，也就是說，rand()函數可以幫我們隨機生成一個由15比特組成的二進位序列。於是我們就可以藉助rand()生成任意長度的二進位序列，接下來把它們拼接出來，就是我們需要生成的隨機數範圍。

/* 此函數生成一個介於0 -0xFFFF FFFF FFFF FFFF之間的無符號，服從均勻分布的隨機整數 */

unsigned long longbbbbigrand()

{

#define UINT64(unsigned long long)

#define MASK0x7FFFull

return( ( (UINT64) rand() &MASK)

((UINT64) rand() &MASK)

( (UINT64) rand() &MASK)

( (UINT64) rand() &MASK)

( (UINT64) rand() &MASK)

#undef MASK

#undefUINT64

}

建議在電腦端查看上述源碼

這大概就是暴力美學吧。

例二：(大小尾端) 對於跨越多個位元組的程序對象（變數等），我們必須規定在內存中如何排列它們。如果最低有效位元組在低地址內存，我們稱之為小端法(little endian)，而如果最低有效位元組在高地址內存，我們稱之為大端法(big endian)。這種稱呼源自格列佛遊記。

對於給定的unsignedlong型數據，請將其轉化為另一尾端表示法。

此題不難，我們僅需取出unsignedlong型(4bytes)中的每個位元組，然後重新組合即可

#define ULunsignedlong

ULEndianTransform(ULn)

{

return( (n &0x000000FFul)

(n &0x0000FF00ul)

(n &0x00FF0000ul) >> 8)

(n &0xFF000000ul) >> 24)

}

#undef UL

例三：(與) 僅使用 ~ (按位取反)和 (按位或) 操作實現 & (按位與).

對於這個問題，我們使用德 · 摩根(De Morgan)定律：

#define ULunsignedlong

ULBitAnd(ULA,ULB)

{

return ~( (~A) (~B) );

}

#undef UL

例四：（藍橋杯某屆省賽題）清除unsigned long型變數尾部連續的1（二進位下）

如： 1011 1100 1100 1011

變為1011 1100 1100 1000

如： 0000 1101 1110 1111

變為 0000 1101 1110 0000

如： 1011 1100 1100 1000

變為 1011 1100 1100 1000（尾部沒有連續的1，不變）

當然用循環肯定可以解決這個問題，但我們要做得更好。我們並不知道需要改變多少個位，因而無法採用固定的掩碼來消除末尾連續的1。對於指定數據n，其掩碼的末尾肯定是一組連續的0，連續0的個數與n末尾的連續1的個數相等。我們考慮將n+1（假設n =1011 1100 1100 1011(二進位) )。

n =1011 1100 1100 1011

n + 1 =1011 1100 1100 1100

對於連續的1，我們只要+1，就可以把他們都變為0，但是此處出現了一個多餘的0(倒數第三位)，如何解決呢？這裡採取與原數做按位與操作的方法。

n + 1 =1011 1100 1100 1100

n & (n+1) =1011 1100 1100 1000

答案就是我們想要的。

#define ULunsignedlong

ULGet(ULA)

{

return A & (A + 1);

}

#undef UL

最後我們來介紹一下算數右移和邏輯右移的區別，還有左移與乘法的關係。

C語言支持所有整型數據的有符號(signed)和無符號(unsigned)運算。C語言默認我們給出的常量是有符號的：

int a; 0x7c

666 087

上面舉例的三個整數和變數a都是有符號型，下面舉例無符號型變數:

unsigned ua; 0x7cu

666U 666u

可以觀察到，對於常量需要加上後綴u或者U，它才會變為無符號常量。C語言允許有符號數與無符號數的轉換，而在轉換過程中，表示這個數的二進位位不變。

longx = -1;

printf("x = %u = %d
", x, x);

printf("u = %u = %d
", u, u);

請運行上述程序，觀察結果。其中 %u 表示按無符號整數輸出，%d表示按有符號整數輸出。

我們通常認為在我們的電腦上，整數由補碼錶示，複習補碼的計算方式：

對於非負數，補碼為其本身；

對於負數，補碼為其本身取反+1；

可以由此來解釋上述程序的運行結果。而據此也不難解釋如下問題：

(unsigned long) -1L < 0

求上述表達式的值

上述表達式的值為. 因為將-1轉為無符號數將不改變其本身的各個二進位位，而 -1 的補碼則是0xFFFFFFFFu，它大於0，因而表達式的值為0。這個地方也告訴我們一個隱含的規則：有符號數與無符號數比較大小，C語言先將有符號數轉化為無符號數，接下來進行兩個無符號數比較大小。

在左移操作 a

這個操作對於有符號數和無符號數是相同的。而C語言對於有符號數和無符號數往往採用不同的右移策略。它們分別被稱之為算數右移和邏輯右移。它們的區別就是，右移後，左邊空出的比特位應該如何填充。

算數右移：填充原數字的最高比特位。

邏輯右移：填充0。

舉例：

0x0123 4567L-(算數右移4bit)->0x0012 3456L

0x8023 4567L-(算數右移4bit)->0xF802 3456L

0x8023 4567L-(邏輯右移4bit)->0x802 3456L

0x0123 4567L-(邏輯右移4bit)->0x0012 3456L

C語言並沒有規定對有符號數做何種右移，然而絕大多數編譯器都將其處理為算術右移；對於無符號數，一定只有邏輯右移。

Reference:

[1] Randal E. Bryant, David R.O" Hallaron. 深入理解計算機系統，第三版；

[2] Jonathan Swift 著, 蔣劍鋒譯. 格列佛遊記，第一卷第4章。

更新預告：

美賽之後才會繼續更新，這幾天作者要閉關修鍊了。大家加油。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！