我們都知道，計算機是使用二進位進行存儲和計算的。十進位的出現是因為人類有十個手指，比較方便表示十進位；而對於計算機而言，因為計算機要依靠電源，而電源只有通電和斷電兩種情況，所以二進位就成為了計算機的基礎進位。
一道送分題
對於二進位，似乎更多的考題是在初賽，但複賽也會涉及到一些內容，而且也可以運用在生活中。
接下來介紹一下二進位數
對於二進位數，首先要知道二進位是什麼。類似於十進位，二進位也是一種進位(廢話)，但二進位運算遵循的規則是「進二」而不是我們熟悉的「進十」。
簡單來說，二進位基數為 2 ，只有 1 和 0
二進位轉十進位
對於一個二進位數，他的十進位數為從左往右的每一位乘上該位數的 2 次方(從第0位開始)，例如
十進位轉二進位
把上面的操作反過來，將十進位數除以 2 直到其為 0 ，每位的餘數即二進位的每一位。
其他進位也可以用類似的方法進行轉換，例題P1143 進位轉換（https://www.luogu.org/problemnew/show/P1143）
原碼、反碼和補碼
原碼，指一個二進位數左邊加上符號位後所得到的碼，且當二進位數大於0時，符號位為0；二進位數小於0時，符號位為1；二進位數等於0時，符號位可以為0或1。
反碼：正數的反碼與其原碼相同；負數的反碼是對其原碼逐位取反，但符號位除外。
補碼：正數的補碼與原碼相同，負數的補碼是其對應正數二進位所有位取反後加1。
在計算機中通常使用補碼進行儲存。
一道例題(2017tg初賽)
先確定該數是負數，然後還原操作得到 01010101=85 ，結果為 -85
--
介紹幾種簡單的位運算
因為計算機使用的是二進位，自然就有獨成一套體系的運算方式，即位運算。
位運算是計算機中最簡潔的運算，並且具有很好用的性質，而且用起來還比較快。總而言之，位運算是十分實用的。
「<<」 「>>」 運算
首先，在這裡這東西跟 cin cout 沒有什麼關係。
在二進位運算中，這東西叫做「左移」「右移」運算，顧名思義，就是將一個二進位數向左或向右移動 k 位，就是給一個數乘 2^k 或者除 2^k (末尾1不計)。
那麼這東西有什麼用呢？這東西快啊
「~」運算
又稱取反運算，就是對一個二進位數按位取反。
對於 int 來說， ~ x=-x-1
那麼這東西有什麼用呢？我也不知道
「&」運算
「&」運算，即「and」 運算，也是一種邏輯運算符，對於二進位運算來說，「&」運算的意義是對於兩個二進位數的每一位，如果這一位都是 1 ，那麼這一位為 1 ，否則這一位為 0 。
舉個例子
10101(21) & 11100(28) = 10100{20}
我們可以用 & 運算判斷一個數是奇數還是偶數，當 x 為奇數時， x 二進位下的第 0 位一定是 1 ，否則為 0 。我們讓 x & 1 ，就可以知道 x 的奇偶性了。
「|」 運算
即 「or」 運算，也是一種邏輯運算符，對於二進位運算來說，「|」 運算的意義是對於兩個二進位數的每一位，如果這兩個數此位有一個 1 那麼此位就是 1 ，否則為 0 。
舉個例子
10101(21) | 11100(28) = 11101(29)
通過對這兩個運算的觀察，我們可以發現一個規律
x & y<=xx | y>=x
根據二進位的性質很容易就可以得出這些結論吧
「^」運算
「^」運算，又稱「xor」運算，異或運算。定義是對於兩個二進位數的每一位，如果相同則為 0 ，否則為 1 。
舉個例子
10101(21) ^ 11100(28) = 1001(9)
異或是一個非常神奇的東東
首先顯而易見的是一個數異或他自己肯定是得 0 的
其次對於一個形如 2n 的數 x ， x ^ 1 =x+1 ,而對於一個形如 2n+1 的數 x ， x ^ 1 =x-1
然後異或運算滿足以下交換律
如果 x ^ y=z 那麼 y ^ z=x ， x ^ z=y
異或運算還是比較常用到的，簡單舉兩個例子
例題一
給你 n 個數，其中只有一個數出現過一次，其餘都成對出現，問只出現過一次的那個數是那個數。
原題 P1469 找筷子（https://www.luogu.org/problemnew/show/P1469）
利用異或的性質 x ^ x=0 ，將所有數異或起來，最後剩下來的那個數就是答案了。
例題二
計算 1 ^ 2 ^ 3 ^ 4 ^ … ^ n 的值
原題 P3908 異或之和（https://www.luogu.org/problemnew/show/P3908）
首先最開始是 1 ，根據異或的性質，我們可以知道 (2n) ^ 1 是等於 2n+1 的
於是我們又回到了 1 ，所以可以得出答案是以 4 為周期循環的。
--
接下來厲害的來了，這三種運算是可以互相轉換的
x|y= ~ (( ~ x) & ( ~ y))
x & y= ~ (( ~ x)|( ~ y))
x ^ y=(x|y)-(x & y)=x+y-((x & y)<<1)
但這東西似乎除了能讓你感受到位運算的博大精深以外似乎什麼用都沒有
運算符的優先級
一道例題(2007tg初賽)
我猜很多人(其實是我)在做這道題的時候果斷選了 18 ，然後掛掉了，答案是 23
你可能會懵逼了(其實還是我)：我沒算錯啊。然後重新算一遍，還是 18
這是因為運算的優先級，本題中會先計算異或運算再計算或運算，也就變成了 23 | 7=23
關於位運算的優先級，大致按下面排序
加減運算 > 移位運算 > 比較大小運算 > 與運算 > 異或運算 > 或運算
如果代碼裡不注意這些細節可能就會出錯
比如對於 k=2^n-1 ，如果想用位運算完成，寫成 k=1<<n-1 就會是錯的
對於拿不準的地方還是加個括號為好
一些常用的位運算小應用
快速交換兩個數
x=x ^ y
y=y ^ x
x=x ^ y
這東西理論上能比正常的交換優一點，當然還是用 swap 吧，畢竟人家什麼都能換，這個只能換整數。
lowbit運算
我們怎樣能夠快速求出一個二進位數位數最低的 1 在哪呢？
根據取反運算的性質， (-x)=( ~ x)+1 ,設 x 最低的 1 所在位是 i ，將 [0,i-1] 全設成 0 ，將 [i+1,31] 位全部取反。
所以我們可以得出 x & (-x)=2^i
主要的應用就是樹狀數組了，這個我不說你們也懂
當然也可以用來計算二進位數中出現了多少個 1
快速判斷奇偶性
這個上面說了，不再多提
在狀壓情況下的操作
先簡單介紹一下狀壓吧。
簡單來說就是使用二進位數來表示某一種狀態來減少儲存的空間，比較常用的有狀壓 DP 和狀壓搜索。在洛谷上可以找到例題。
而狀壓比較常用的操作有
更多奇奇怪怪的應用可視題目要求所定。另外別的進位也可以用來做狀態壓縮，但是運算起來就沒那麼方便了，也視情況所定。
快速冪
快速冪顧名思義，就是快速算某個數的多少次冪。
求 x^n 的值，我們最樸素的算法是 O(n) 的，而快速冪可以將複雜度優化到 O(log^n)
大致過程是把 n 轉換成二進位，判斷這一位是 1 還是 0 ，然後進行操作
舉個例子 當 n=11 時， a^{11}=a^{}(2^0+2^1+2^3)
大致代碼如下
小計算加速
前面說過了位運算的速度是比四則運算快的，所以可以用來稍稍的加一點速，比如對於二分的過程
mid=(l+r)/2
我們就可以寫成
mid=(l+r)>>1
或者在使用線段樹的時候
build(p2,l,mid);build(p2+1,mid+1,r)
我們可以寫成
build(p<<1,l,mid);build(p<<1|1,mid+1,r)
你要相信，這種寫法真的不是在嘚瑟，這樣真的會快那麼一點的，說不定這麼一點常數就能讓你卡過一道題
bitset
bitset 是 C++ 裡的一個類，我們可以簡單認為它就是一個 01 數組，可以對數組的每一位進行賦值，但它還支持很多神奇的操作，比如前面介紹過的位運算，比如 「&」 運算和 「|」 運算，但相比較於用數組完成， bitset 會在時間上佔很大的優勢。
bitset 在定義的時候一定要定義大小，特殊的是需要使用尖括號，如下。
bitset<1000> Bitset
舉一個例子 P2347 砝碼承重（https://www.luogu.org/problemnew/show/P2347）
這道題似乎是一個 DP 題，但巧妙的應用 bitset 的性質也可以完成。
因為 bitset 只能存 0 和 1 ，我們可以讓第 i 位為 1 來表示可以表示出 i 這個值。
bitset能對某一位賦值，我們初始定義 Bitset[0]=1 ，表示可以表示出 0
當我們加入一個新的砝碼的時候，我們將這個砝碼加入 bitset ，即進行如下的操作
Bitset |= Bitset << w[i]
簡單理解就是已有的所有能表示出的值都加上 w_i 再與原集合取併集。
最後我們統計 bitset 中有多少個 1 即可，可以使用自帶函數 Bitset.count() 完成。
bitset 還有一些自帶函數，例如 Bitset.any() 返回是否有 1 ， Bitset.set() 可以將全部位置賦成 1 等等，大多都是一些二進位操作。
bitset 的複雜度：因為bitset是用 uint/long long 類型來實現每次同時操作 32/64 個 01 變量的東西，所以他的很多操作都是 O(1) 或 O(n/32) / O(n/64) 的。至於是 32 還是 64 ，一般看機器是32位還是64位
builtin內置函數
GCC提供了一系列的builtin函數，可以實現一些簡單快捷的功能來方便程序編寫，簡單介紹幾種常用的。
有些函數會直接把 x 轉成 unsigned 型
int __builtin_ctz(x) //返回 x 二進位表示下後導 0 的個數//帶 0 的話會出32int __builtin_clz(x) //返回 x 二進位表示下前導 0 的個數//因為轉成了 unsigned 帶 1 的話是 31，帶 2147483648 得 0，不過帶 0 還是得 31int __builtin_ffs(x) //返回二進位下最後一個 1 的位置。//一般情況下就是 ctz+1int __builtin_popcount(x) //返回 x 二進位表示下有多少位是 1int __builtin_parity(x) //返回 x 二進位下 1 的個數的奇偶性。
以上函數的 long long 版本只需要再函數後面加上 ll 即可
例如：
__builtin_ctzll(x)
這些函數是 gcc 自帶的，不需要額外頭文件。
二進位和位運算都屬於比較簡單的問題，經常活躍在初賽上，而對於複賽則比較基礎了，我們更多的是利用二進位的一些性質優化複雜度和完成代碼。
最後分享一個關於狀態壓縮的問題，來自於編程之美。
此時象棋棋盤上只剩下雙方的將帥，我們知道將和帥是不能面對對方的，請用一個變量表示所有合法的狀況。
我們可以使用一個長度為 18 的二進位數，通過把九宮格壓成一行，用前九位表示將的位置，後九位表示帥的位置。
有沒有更簡單的辦法呢？
給九宮格的每一個位置一個標號，可以用兩位的十進位數表示將和帥的位置。
你還有別的辦法嗎？
本文發布於洛穀日報，特約作者：chengni
原文地址：https://www.luogu.org/blog/chengni5673/er-jin-zhi-yu-wei-yun-suan