一、前言

??今天主要內容是聊一聊二進制和位運算，
??對應視頻教程如下：位運算視頻教程，

二、再談二進制

??我們在學習 光天化日學C語言（06）- 進制轉換入門 的時候，曾經提到過二進制，
??二進制就是逢二進一，計算機中的存盤采用的就是二進制，在計算機中，非零即一，

1、二進制數值表示

??例如，在計算機中，我們可以用單純的 0 和 1 來表示數字，

1、101、1100011、100101010101 都是二進制數，
123、423424324、101020102101AF 則不是，因為有 0 和 1 以外的數字位，

??一般為了不產生二義性，我們會在數字的右下角寫上它的進制，例如： 101 0 ( 10 ) 1010_{(10)} 1010(10)???代表的是十進制下的 1010，也就是十進制下的 “一千零一十”， 101 0 ( 2 ) 1010_{(2)} 1010(2)???代表的是二進制下的 1010，也就是十進制下的 “十”，

2、二進制加法

??二進制加法采用從低到高的位依次相加，當相加的和為2時，則向高位進位，

??例如，在二進制中，加法如下： 1 ( 2 ) + 1 ( 2 ) = 1 0 ( 2 ) 1 ( 2 ) + 0 ( 2 ) = 1 ( 2 ) 0 ( 2 ) + 1 ( 2 ) = 1 ( 2 ) 0 ( 2 ) + 0 ( 2 ) = 0 ( 2 ) 1_{(2)} + 1_{(2)} = 10_{(2)} \\ 1_{(2)} + 0_{(2)} = 1_{(2)} \\ 0_{(2)} + 1_{(2)} = 1_{(2)} \\ 0_{(2)} + 0_{(2)} = 0_{(2)} 1(2)?+1(2)?=10(2)?1(2)?+0(2)?=1(2)?0(2)?+1(2)?=1(2)?0(2)?+0(2)?=0(2)?

3、二進制減法

??二進制減法采用從低到高的位依次相減，當遇到 0 減 1 的情況，則向高位借位，

??例如，在二進制中：減法如下： 1 ( 2 ) ? 1 ( 2 ) = 0 ( 2 ) 1 ( 2 ) ? 0 ( 2 ) = 1 ( 2 ) 1 0 ( 2 ) ? 1 ( 2 ) = 1 ( 2 ) 0 ( 2 ) ? 0 ( 2 ) = 0 ( 2 ) 1_{(2)} - 1_{(2)} = 0_{(2)} \\ 1_{(2)} - 0_{(2)} = 1_{(2)} \\ 10_{(2)} - 1_{(2)} = 1_{(2)} \\ 0_{(2)} - 0_{(2)} = 0_{(2)} 1(2)??1(2)?=0(2)?1(2)??0(2)?=1(2)?10(2)??1(2)?=1(2)?0(2)??0(2)?=0(2)???而我們今天要講的位運算正是基于二進制展開的，

三、位運算簡介

??位運算可以理解成對二進制數字上的每一個位進行操作的運算，位運算分為 邏輯（布爾）位運算子 和 移位位運算子，
??邏輯位運算子又分為 位與(&)、位或(|)、異或(^)、按位取反(~)；移位位運算子分為 左移(<<) 和 右移(>>)，
??如圖所示：

1、位與的定義

??位與運算子是一個二元的位運算子，也就是有兩個運算元，表示為x & y，
??位與運算會對運算元的每一位按照如下表格進行運算，對于每一位只有 0 或 1 兩種情況，所以組合出來總共 2 2 = 4 2^2 = 4 22=4 種情況，

??通過這個表，我們得出一些結論：
??1）無論是 0 或 1，只要位與上 1，還是它本身；
??2）無論是 0 或 1，只要位與上 0，就變成 0；

#include <stdio.h>
int main() {
    int a = 0b1010;           // (1)
    int b = 0b0110;           // (2)
    printf("%d\n", (a & b) ); // (3)
    return 0;
}

• ( 1 ) (1) (1) 在C語言中，以0b作為前綴，表示這是一個二進制數，那么a的實際值就是 ( 1010 ) 2 (1010)_2 (1010)2?，
• ( 2 ) (2) (2) 同樣的，b的實際值就是 ( 0110 ) 2 (0110)_2 (0110)2?；
• ( 3 ) (3) (3) 那么這里a & b就是對 ( 1010 ) 2 (1010)_2 (1010)2? 和 ( 0110 ) 2 (0110)_2 (0110)2? 的每一位做表格中的&運算，

??所以最后輸出結果為：2
??因為輸出的是十進制數，它的二進制表示為： ( 0010 ) 2 (0010)_2 (0010)2?，注意：這里的 前導零 可有可無，作者寫上前導零只是為了對齊以及讓讀者更加清楚位與的運算方式，

2、位與運算子的簡單應用

1）奇偶性判定

??我們判斷一個數是奇數還是偶數，往往是通過取模%來判斷的，如下：

#include <stdio.h>
int main() {
    if(5 % 2 == 1) {
        printf("5是奇數\n");
    }
    if(6 % 2 == 0) {
        printf("6是偶數\n");
    }
    return 0;
} 

??然而，我們也可以這么寫：

#include <stdio.h>
int main() {
    if(5 & 1) {
        printf("5是奇數\n");
    }
    if( (6 & 1) == 0 ) {
        printf("6是偶數\n");
    }
    return 0;
} 

??這是利用了奇數和偶數分別的二進制數的特性，如下表所示：

??所以，我們對任何一個數，通過將它和 0b1進行位與，結果為零，則必然這個數的二進制末尾位為0，根據以上表就能得出它是偶數了；否則，就是奇數，

2）取末五位

給定一個數，求它的二進制表示的末五位，以十進制輸出即可，

??這個問題的核心就是：我們只需要末五位，剩下的位我們是不需要的，所以可以將給定的數 位與上0b11111，這樣一來就直接得到末五位的值了，代碼實作如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", (x & 0b11111) );
    return 0;
} 

3）消除末尾五位

給定一個 32 位整數，要求消除它的末五位，

??還是根據位與的性質，消除末五位的含義，有兩層：
??1）末五位，要全變成零；
??2）剩下的位不變；
??那么，根據位運算的性質，我們需要數，它的高27位都為1，低五位都為 0，則這個數就是： ( 11111111111111111111111111100000 ) 2 (11111111111111111111111111100000)_2 (11111111111111111111111111100000)2???但是如果要這么寫，代碼不瘋掉，人也會瘋掉，所以一般我們把它轉成十六進制，每四個二進制位可以轉成一個十六進制數，所以得到十六進制數為0xffffffe0，代碼實作如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", (x & 0xffffffe0) );
    return 0;
} 

4）2的冪判定

請用一句話，判斷一個正數是不是2的冪，

??如果一個數是 2 的冪，它的二進制表示必然為以下形式： 1 00...00 ? k 1\underbrace{00...00}_{\rm k} 1k 00...00?? 這個數的十進制值為 2 k 2^k 2k，那么我們將它減一，即 2 k ? 1 2^k-1 2k?1 的二進制表示如下（參考二進制減法的借位）： 0 11...11 ? k 0\underbrace{11...11}_{\rm k} 0k 11...11??于是 這兩個數位與的結果為零，于是我們就知道了如果一個數 x x x 是 2 的冪，那么x & (x-1)必然為零，而其他情況則不然，
??所以本題的答案為：

	(x & (x-1)) == 0

3、位或的定義

??位或運算子是一個二元的位運算子，也就是有兩個運算元，表示為x | y，
??位或運算會對運算元的每一位按照如下表格進行運算，對于每一位只有 0 或 1 兩種情況，所以組合出來總共 2 2 = 4 2^2 = 4 22=4 種情況，

??通過這個表，我們得出一些結論：
??1）無論是 0 或 1，只要位或上 1，就變成1；
??2）只有當兩個運算元都是0的時候，才變成 0；

#include <stdio.h>
int main() {
    int a = 0b1010;           // (1)
    int b = 0b0110;           // (2)
    printf("%d\n", (a | b) ); // (3)
    return 0;
}

• ( 1 ) (1) (1) 在C語言中，以0b作為前綴，表示這是一個二進制數，那么a的實際值就是 ( 1010 ) 2 (1010)_2 (1010)2?，
• ( 2 ) (2) (2) 同樣的，b的實際值就是 ( 0110 ) 2 (0110)_2 (0110)2?；
• ( 3 ) (3) (3) 那么這里a | b就是對 ( 1010 ) 2 (1010)_2 (1010)2? 和 ( 0110 ) 2 (0110)_2 (0110)2? 的每一位做表格中的|運算，

??所以最后輸出結果為：14
??因為輸出的是十進制數，它的二進制表示為： ( 1110 ) 2 (1110)_2 (1110)2?，

4、位或運算子的簡單應用

1）設定標記位

【例題1】給定一個數，判斷它二進制低位的第 5 位，如果為 0，則將它置為 1，

??這個問題，我們很容易聯想到位或，
??我們分析一下題目意思，如果第 5 位為 1，不用進行任何操作；如果第 5 位為 0，則置為 1，言下之意，無論第五位是什么，我們都直接置為 1即可，代碼如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x | 0b10000); 
    return 0;
}

2）置空標記位

【例題2】給定一個數，判斷它二進制低位的第 5 位，如果為 1，則將它置為 0，

??這個問題，我們在學過 《演算法零基礎100講》(第42講) 位運算 (位與) 入門 以后，很容易得出這樣一種做法：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x & 0b11111111111111111111111111101111); 
    return 0;
}

??其它位不能變，所以位與上1；第5位要置零，所以位與上0；
??這樣寫有個問題，就是這串數字太長了，一點都不美觀，而且容易寫錯，當然我們也可以轉換成 十六進制，轉換的程序也有可能出錯，
??而我們利用位或，只能將第5位設定成1，怎么把它設定成0呢？

我們可以配合減法來用，分成以下兩步：
??1）首先，強行將低位的第5位置成1；
??2）然后，強行將低位的第5位去掉；

??第 ( 1 ) (1) (1) 步可以采用位或運算，而第 ( 2 ) (2) (2) 步，我們可以直接用減法即可，代碼實作如下：

#include <stdio.h>
int main() {
    int x;
    int a = 0b10000; 
    scanf("%d", &x);
    printf("%d\n", (x | a) - a ); 
    return 0;
}

??注意：直接減是不行的，因為我們首先要保證那一位為 1，否則貿然級訓產生借位，和題意不符，

5、異或運算子的定義

??異或運算子是一個二元的位運算子，也就是有兩個運算元，表示為x ^ y，
??異或運算會對運算元的每一位按照如下表格進行運算，對于每一位只有 0 或 1 兩種情況，所以組合出來總共 2 2 = 4 2^2 = 4 22=4 種情況，

??通過這個表，我們得出一些結論：
??1）兩個相同的十進制數異或的結果一定為零，
??2）任何一個數和 0 的異或結果一定是它本身，
??3）異或運算滿足結合律和交換律，

#include <stdio.h>
int main() {
    int a = 0b1010;           // (1)
    int b = 0b0110;           // (2)
    printf("%d\n", (a ^ b) ); // (3)
    return 0;
}

• ( 1 ) (1) (1) 在C語言中，以0b作為前綴，表示這是一個二進制數，那么a的實際值就是 ( 1010 ) 2 (1010)_2 (1010)2?，
• ( 2 ) (2) (2) 同樣的，b的實際值就是 ( 0110 ) 2 (0110)_2 (0110)2?；
• ( 3 ) (3) (3) 那么這里a ^ b就是對 ( 1010 ) 2 (1010)_2 (1010)2? 和 ( 0110 ) 2 (0110)_2 (0110)2? 的每一位做表格中的^運算，

??所以最后輸出結果為：12，因為輸出的是十進制數，它的二進制表示為： ( 1100 ) 2 (1100)_2 (1100)2?，

6、異或運算子的應用

1）標記位取反

【例題1】給定一個數，將它的低位數起的第 4 位取反，0 變 1，1 變 0，

??這個問題，我們很容易聯想到異或，我們分析一下題目意思，如果第 4 位為 1，則讓它異或上 0b1000就能變成 0；如果第 4 位 為 0，則讓它異或上 0b1000就能變成 1，也就是無論如何都是異或上 0b1000，代碼如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x ^ 0b1000); 
    return 0;
}

2）變數交換

【例題2】給定兩個數 a a a 和 b b b，用異或運算交換它們的值，

??這個是比較老的面試題了，直接給出代碼：

#include <stdio.h>
int main() {
    int a, b;
	while (scanf("%d %d", &a, &b) != EOF) {
	    a = a ^ b;   // (1)
	    b = a ^ b;   // (2)
	    a = a ^ b;   // (3)
	    printf("%d %d\n", a, b);
	}
	return 0;
}

??我們直接來看 ( 1 ) (1) (1) 和 ( 2 ) (2) (2) 這兩句話，相當于b等于a ^ b ^ b，根據異或的幾個性質，我們知道，這時候的b的值已經變成原先a的值了，
??而再來看第 ( 3 ) (3) (3) 句話，相當于a等于a ^ b ^ a，還是根據異或的幾個性質，這時候，a的值已經變成了原先b的值，
??從而實作了變數a和b的交換，

3）出現奇數次的數

【例題3】輸入 n n n 個數，其中只有一個數出現了奇數次，其它所有數都出現了偶數次，求這個出現了奇數次的數，

??根據異或的性質，兩個一樣的數異或結果為零，也就是所有出現偶數次的數異或都為零，那么把這 n n n 個數都異或一下，得到的數就一定是一個出現奇數次的數了，

#include <stdio.h>
int main() {
    int n, x, i, ans;
    scanf("%d", &n);
    ans = 0;
    for(i = 0; i < n; ++i) {
        scanf("%d", &x);
        ans = (ans ^ x);
    } 
    printf("%d\n", ans);
    return 0;
}

??光天化日學C語言（14）- 位運算 & 的應用
??光天化日學C語言（15）- 位運算 | 的應用
??光天化日學C語言（16）- 位運算 ^ 的應用
??光天化日學C語言（17）- 位運算 ~ 的應用
??光天化日學C語言（18）- 位運算 << 的應用
??光天化日學C語言（19）- 位運算 >> 的應用

四、位運算概覽

??今天，我們先來對位運算進行一個初步的介紹，后面會對每個運算子的應用做詳細介紹，包括刷題的時候如何運用位運算來加速等等，

1、邏輯位運算

??對于布爾位運算，總共有四個，如下表所示：

1）位與

??位與就是對運算元的每一位按照如下表格進行運算，對于每一位只有 0 或 1 兩種情況，所以組合出來總共 2 2 = 4 2^2 = 4 22=4 種情況，

#include <stdio.h>
int main() {
    int a = 0b1010;           // (1)
    int b = 0b0110;           // (2)
    printf("%d\n", (a & b) ); // (3)
    return 0;
}

• ( 1 ) (1) (1) 在C語言中，以0b作為前綴，表示這是一個二進制數，那么a的實際值就是 ( 1010 ) 2 (1010)_2 (1010)2?，
• ( 2 ) (2) (2) 同樣的，b的實際值就是 ( 0110 ) 2 (0110)_2 (0110)2?；
• ( 3 ) (3) (3) 那么這里a & b就是對 ( 1010 ) 2 (1010)_2 (1010)2? 和 ( 0110 ) 2 (0110)_2 (0110)2? 的每一位做表格中的&運算，
• 所以最后輸出結果為：

2

??因為輸出的是十進制數，它的二進制表示為： ( 0010 ) 2 (0010)_2 (0010)2?，
??注意：這里的 前導零 可有可無，作者寫上前導零只是為了對齊以及讓讀者更加清楚位與的運算方式，

2）位或

??位或的運算結果如下：

??我們來看以下這段程式：

#include <stdio.h>
int main() {
    int a = 0b1010;
    int b = 0b0110;         
    printf("%d\n", (a | b) );
    return 0;
}

??以上程式的輸出結果為：

14

??即二進制下的 ( 1110 ) 2 (1110)_2 (1110)2? ，

3）異或

??異或的運算結果如下：

??我們來看以下這段程式：

#include <stdio.h>
int main() {
    int a = 0b1010;       
    int b = 0b0110;          
    printf("%d\n", (a ^ b) ); 
    return 0;
}

??以上程式的輸出結果為：

12

??即二進制下的 ( 1100 ) 2 (1100)_2 (1100)2? ，

4）按位取反

??按位取反其實就是 0 變 1， 1 變 0，
??同樣，我們來看一段程式，

#include <stdio.h>
int main() {
    int a = 0b1;
    printf("%d\n", ~a );
    return 0;
}

??這里我想賣個關子，同學們可以自己試一下運行結果，
??至于為什么會輸出這個結果，我會在 光天化日學C語言（17）- 位運算 ~ 的應用 中進行詳細講解，

2、移位位運算

??對于移位位運算，總共有兩個，如下表所示：

1）左移

??其中x << y代表將二進制的 x x x 的末尾添加 y y y 個零，就好比向左移動了 y y y 位，
??比如 ( 1011 ) 2 (1011)_2 (1011)2? 左移三位的結果為： ( 1011000 ) 2 (1011000)_2 (1011000)2?，

2）右移

??其中x >> y代表將二進制的 x x x 從右邊開始截掉 y y y 個數，就好比向右移動了 y y y 位，
??比如 ( 101111 ) 2 (101111)_2 (101111)2? 右移三位的結果為： ( 101 ) 2 (101)_2 (101)2?，