這周是本學期上課周倒數第三周啦，為了讓同學們面對程設作業和考試時更加從容，本期我們將介紹兩套使用較廣的工具：位運算 和 STL庫
位運算本來以為同學們對位運算完全不了解，結果隨機採訪了幾位同學：
根據我們樣本數高達
因此我們普及位運算變得十分必要（大霧
基本定義為了方便後面的實例運用，還是先回顧一下簡單的定義
與(&)、或(|)、非(~)在c++中並不一定需要用到符號，也可以使用關鍵字(c++11標準)進行相應的運算按位與(&)：可用 bitand（一定不要只寫 and，這是邏輯與的意思）按位或(|)：可用 bitor（一定不要只寫 or，這是邏輯或的意思）小編暫時不清楚取反運算符有什麼關鍵字代替，歡迎大家在後臺留言當然是否使用關鍵字代替符號是大家的自由，但是其中的關鍵字能幫助我們理解這個運算，以按位與為例bitand=bit+and：
按位或和取反類似，但值得注意的是，當我們進行位運算的對象是 int 類型或者 short 類型等前面沒有加 unsigned 前綴的類型時，計算機儲存時會留出最高的二進位位用於儲存符號。
如 int 是
將二進位位向左/右平移若干位……
值得注意的是，由於儲存是有限的，故我們還需要考慮溢出的問題，這時，我們定義：
如，對於
以上運算都有對應算符 &=,^=,<<=等……
奇妙應用雖然有些人會說，你這位運算也沒用。我說我這有用，這是底層運算，四兩撥千斤。兩百多行的if語句，都扳不過我的幾個位運算……
1. 計算眾所周知，在不考慮符號和溢出截斷時，當位置的每一位向左移動
相應的，x >>= k 相當於將 x 整除了
而由於底層實現原因，位運算的速度比加減乘除運算快了不少 （當然這並不能成為你程序寫得醜的理由）
一般情況下，同級數字進行各類運算的運行時間有：位運算<加減<乘法<除法（經驗之談）2. 交換函數平時大家使用的交換函數大多是藉助臨時變量進行交換：
int c = a;
a = b;
b = c;但實際上，我們利用位運算可以避免創建新變量：
a ^= b;
b ^= a;
a ^= b;具體的原理大家可以自行思索qwq
哦對，講實話，其實不用位運算也是可以避免創建新變量的orz
當然，這講實話只是一個稍顯「炫技」的技巧，平時臨時變量還是挺香的（感覺位運算非常適合出各種作業題，比如 「如何利用位運算快速取出變量低位連續的
」） 有興趣的同學可以自行取用：http://graphics.stanford.edu/~seander/bithacks.html#OperationCounting
3. 狀態壓縮講實話這才是我寫這篇推送的原因qwq
五個同學過一條河，河中只有一條船，並且船上一次最多只能乘兩個人。A,B,C,D,E同學過河分別需要1,3,6,8,12分鐘，過河的速度由過河最慢者決定。要求這五位同學必須在30分鐘內全部渡河，問他們如何過河？（徐老師第十三次作業第二題）
在這道題中，使用狀態壓縮能非常方便地儲存搜索狀態：（五個人分別在河的哪一岸，船的位置）
相信大多數同學第一想法是直接保存
個元素（五個元素對應五個人的位置+一個元素保存船的位置） void dfs(int A, int B, ..., int boat, int time)或是運用指針引用數組
void dfs(int *position)雖然這題的工作量並不大，但懶癌晚期患者的第一想法仍然是狀態壓縮——只需保存一個 int 值即可
具體的做法是，由於每一個人的狀態只可能在左岸(記為0)或是右岸(記為1)，每一個人其實只需要一個bit位即可，那麼可以只記錄一個數字
： 的二進位最低位即為 的狀態，可使用 x&1 提取出來 的低位第二位為 的狀態，可使用 x&2 提取出來-記得提取出來的是 或 ，使用 (x>>1)&1 即可提取出 或 啦 的低位第三位為 的狀態，可使用 (x>>2)&1 提取出來 那麼函數引用就變得非常簡單：
void dfs(int S)同時，當第
名同學渡河時（可能從 變成 ，也可能 變成 ），狀態改變實現變得非常簡單：S^(1<<i) 兩位同學一起渡河也很簡單：S^(1<<i)^(1<<j)
由於作業還未結束，故這裡不放完整的代碼實現了（如有需要可以在公眾號後臺諮詢）
一個
西洋棋棋盤，在上面放置 個皇后，使它們互不攻擊，問有多少種擺放方式（ 皇后問題） 這種問題一般使用搜索解決，但在搜索過程中，皇后的斜向攻擊佔位方式非常適合位運算中的移位運算，所以就有了這道題的不用數組版本（獻醜貼上自己的代碼qwq）：
int Search(const int n, int s, int ld, int rd, int col) {
if (s > n) return 1;
int res = 0;
for (int i = 1; i < (1<<n); i <<= 1) {
if (i & (col | ld | rd)) continue;
res += Search(n, s+1, (ld|i) << 1, (rd|i) >> 1, col|i);
}
return res;
}
int main() {
int n;
std::cin >> n;
std::cout << Search(n, 1, 0, 0, 0);
return 0;
}當然，拿位運算來做這種簡單的事情有點委屈它老人家，這種將狀態壓縮至一個整數裡的方法有其更大功效，在動態規劃中廣泛使用（有興趣的同學可以自行搜索「狀壓dp」） 在魔方大作業中也有作用
當然位運算還有一大堆奇葩應用，這裡只是選取的一些同學們程設考試中可以使用到的一部分內容。
當然如果有其他需求歡迎留言，可能被我們選定為後期推送的主題！