位運算

位運算就是基於整數的二進制表示進行的運算。由於計算機內部就是以二進制來存儲數據，位運算是相當快的。

基本的位運算共 \(6\) 種，分別為按位與、按位或、按位異或、按位取反、左移和右移。

為了方便敍述，下文中省略「按位」。

與、或、異或

這三者都是兩數間的運算，因此在這裏一起講解。

它們都是將兩個整數作為二進制數，對二進制表示中的每一位逐一運算。

運算	運算符	數學符號表示	解釋
與	`&`	\(\&\)、\(\operatorname{and}\)	只有兩個對應位都為 \(1\) 時才為 \(1\)
或	`\|`	\(\mid\)、\(\operatorname{or}\)	只要兩個對應位中有一個 \(1\) 時就為 \(1\)
異或	`^`	\(\oplus\)、\(\operatorname{xor}\)	只有兩個對應位不同時才為 \(1\)

注意區分邏輯與（對應的數學符號為 \(\wedge\)）和按位與、邏輯或（\(\vee\)）和按位或的區別。網絡中的資料中使用的符號多有不規範之處，以上下文為準。

異或運算的逆運算是它本身，也就是説兩次異或同一個數最後結果不變，即 \(a \oplus b \oplus b = a\) 。

舉例：

\[ \begin{aligned} 5 &=(101)_2\\ 6 &=(110)_2\\ 5\operatorname\&6 &=(100)_2 =\ 4\\ 5\operatorname|6 &=(111)_2 =\ 7\\ 5\oplus6 &=(011)_2 =\ 3\\ \end{aligned} \]

取反

取反是對一個數 \(num\) 進行的位運算，即單目運算。

取反暫無默認的數學符號表示，其對應的運算符為 ~。它的作用是把 \(num\) 的二進制補碼中的 \(0\) 和 \(1\) 全部取反（\(0\) 變為 \(1\)，\(1\) 變為 \(0\)）。有符號整數的符號位在 ~ 運算中同樣會取反。

補碼：在二進制表示下，正數和 \(0\) 的補碼為其本身，負數的補碼是將其對應正數按位取反後加一。

舉例（有符號整數）：

\[ \begin{aligned} 5&=(00000101)_2\\ \text{~}5&=(11111010)_2=-6\\ -5\text{ 的補碼}&=(11111011)_2\\ \text{~}(-5)&=(00000100)_2=4 \end{aligned} \]

左移和右移

num << i 表示將 \(num\) 的二進制表示向左移動 \(i\) 位所得的值。

num >> i 表示將 \(num\) 的二進制表示向右移動 \(i\) 位所得的值。

舉例：

\[ \begin{aligned} 11&=(00001011)_2\\ 11<<3&=(01011000)_2=88\\ 11>>2&=(00000010)_2=2 \end{aligned} \]

移位運算中如果出現如下情況，則其行為未定義：

右操作數（即移位數）為負值；
右操作數大於等於左操作數的位數；

例如，對於 int 類型的變量 a ， a<<-1 和 a<<32 都是未定義的。

對於左移操作，需要確保移位後的結果能被原數的類型容納，否則行為也是未定義的。¹對一個負數執行左移操作也未定義。²

對於右移操作，右側多餘的位將會被捨棄，而左側較為複雜：對於無符號數，會在左側補 \(0\)；而對於有符號數，則會用最高位的數（其實就是符號位，非負數為 \(0\)，負數為 \(1\)）補齊。³

複合賦值位運算符

和 += , -= 等運算符類似，位運算也有複合賦值運算符： &= , |= , ^= , <<= , >>= 。（取反是單目運算，所以沒有。）

關於優先級

位運算的優先級低於算術運算符（除了取反），而按位與、按位或及異或低於比較運算符（詳見 C++ 運算符優先級總表），所以使用時需多加註意，在必要時添加括號。

位運算的應用

位運算一般有三種作用：

高效地進行某些運算，代替其它低效的方式。
表示集合（常用於狀壓 DP）。
題目本來就要求進行位運算。

需要注意的是，用位運算代替其它運算方式（即第一種應用）在很多時候並不能帶來太大的優化，反而會使代碼變得複雜，使用時需要斟酌。（但像「乘 2 的非負整數次冪」和「除以 2 的非負整數次冪」就最好使用位運算，因為此時使用位運算可以優化複雜度。）

有關 2 的冪的應用

由於位運算針對的是變量的二進制位，因此可以推廣出許多與 2 的整數次冪有關的應用。

將一個數乘（除） 2 的非負整數次冪：

C++Python

int mulPowerOfTwo(int n, int m) {  // 計算 n*(2^m)
  return n << m;
}
int divPowerOfTwo(int n, int m) {  // 計算 n/(2^m)
  return n >> m;
}

def mulPowerOfTwo(n, m): # 計算 n*(2^m)
    return n << m
def divPowerOfTwo(n, m): # 計算 n/(2^m)
    return n >> m

Warning

我們平常寫的除法是向 \(0\) 取整，而這裏的右移是向下取整（注意這裏的區別），即當數大於等於 \(0\) 時兩種方法等價，當數小於 \(0\) 時會有區別，如： -1 / 2 的值為 \(0\) ，而 -1 >> 1 的值為 \(-1\) 。

取絕對值

在某些機器上，效率比 n > 0 ? n : -n 高。

C++Python

int Abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
  /* n>>31 取得 n 的符號，若 n 為正數，n>>31 等於 0，若 n 為負數，n>>31 等於 -1
    若 n 為正數 n^0=n, 數不變，若 n 為負數有 n^(-1)
    需要計算 n 和 -1 的補碼，然後進行異或運算，
    結果 n 變號並且為 n 的絕對值減 1，再減去 -1 就是絕對值 */
}

def Abs(n):
    return (n ^ (n >> 31)) - (n >> 31)
    """
    n>>31 取得 n 的符號，若 n 為正數，n>>31 等於 0，若 n 為負數，n>>31 等於 -1
    若 n 為正數 n^0=n, 數不變，若 n 為負數有 n^(-1)
    需要計算 n 和 -1 的補碼，然後進行異或運算，
    結果 n 變號並且為 n 的絕對值減 1，再減去 -1 就是絕對值
    """

取兩個數的最大/最小值

在某些機器上，效率比 a > b ? a : b 高。

C++Python

// 如果 a >= b, (a - b) >> 31 為 0，否則為 -1
int max(int a, int b) { return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31)); }
int min(int a, int b) { return (a & ((a - b) >> 31)) | (b & (~(a - b) >> 31)); }

# 如果 a >= b, (a - b) >> 31 為 0，否則為 -1
def max(a, b):
    return b & ((a - b) >> 31) | a & (~(a - b) >> 31)
def min(a, b):
    return a & ((a - b) >> 31) | b & (~(a - b) >> 31)

判斷兩非零數符號是否相同

C++Python

bool isSameSign(int x, int y) {  // 有 0 的情況例外
  return (x ^ y) >= 0;
}

# 有 0 的情況例外
def isSameSign(x, y):
    return (x ^ y) >= 0

交換兩個數

該方法具有侷限性

這種方式只能用來交換兩個整數，使用範圍有限。

對於一般情況下的交換操作，推薦直接調用 algorithm 庫中的 std::swap 函數。

void swap(int &a, int &b) { a ^= b ^= a ^= b; }

操作一個數的二進制位

獲取一個數二進制的某一位：

C++Python

// 獲取 a 的第 b 位，最低位編號為 0
int getBit(int a, int b) { return (a >> b) & 1; }

# 獲取 a 的第 b 位，最低位編號為 0
def getBit(a, b):
    return (a >> b) & 1

將一個數二進制的某一位設置為 \(0\)：

C++Python

// 將 a 的第 b 位設置為 0 ，最低位編號為 0
int unsetBit(int a, int b) { return a & ~(1 << b); }

# 將 a 的第 b 位設置為 0 ，最低位編號為 0
def unsetBit(a, b):
    return a & ~(1 << b)

將一個數二進制的某一位設置為 \(1\)：

C++Python

// 將 a 的第 b 位設置為 1 ，最低位編號為 0
int setBit(int a, int b) { return a | (1 << b); }

# 將 a 的第 b 位設置為 1 ，最低位編號為 0
def setBit(a, b):
    return a | (1 << b)

將一個數二進制的某一位取反：

C++Python

// 將 a 的第 b 位取反 ，最低位編號為 0
int flapBit(int a, int b) { return a ^ (1 << b); }

# 將 a 的第 b 位取反 ，最低位編號為 0
def flapBit(a, b):
    return a ^ (1 << b)

這些操作相當於將一個 \(32\) 位整型變量當作一個長度為 \(32\) 的布爾數組。

漢明權重

漢明權重是一串符號中不同於（定義在其所使用的字符集上的）零符號（zero-symbol）的個數。對於一個二進制數，它的漢明權重就等於它 \(1\) 的個數（即 popcount）。

求一個數的漢明權重可以循環求解：我們不斷地去掉這個數在二進制下的最後一位（即右移 \(1\) 位），維護一個答案變量，在除的過程中根據最低位是否為 \(1\) 更新答案。

代碼如下：

// 求 x 的漢明權重
int popcount(int x) {
    int cnt = 0;
    while (x) {
        cnt += x & 1;
        x >>= 1;
    }
    return cnt;
}

求一個數的漢明權重還可以使用 lowbit 操作：我們將這個數不斷地減去它的 lowbit⁴，直到這個數變為 \(0\)。

代碼如下：

// 求 x 的漢明權重
int popcount(int x) {
    int cnt = 0;
    while (x) {
        cnt++;
        x -= x & -x;
    }
    return cnt;
}

構造漢明權重遞增的排列

在狀壓 DP 中，按照 popcount 遞增的順序枚舉有時可以避免重複枚舉狀態。這是構造漢明權重遞增的排列的一大作用。

下面我們來具體探究如何在 \(O(n)\) 時間內構造漢明權重遞增的排列。

我們知道，一個漢明權重為 \(n\) 的最小的整數為 \(2^n-1\)。只要可以在常數時間構造出一個整數漢明權重相等的後繼，我們就可以通過枚舉漢明權重，從 \(2^n-1\) 開始不斷尋找下一個數的方式，在 \(O(n)\) 時間內構造出 \(0\sim n\) 的符合要求的排列。

而找出一個數 \(x\) 漢明權重相等的後繼有這樣的思路，以 \((10110)_2\) 為例：

把 \((10110)_2\) 最右邊的 \(1\) 向左移動，如果不能移動，移動它左邊的 \(1\)，以此類推，得到 \((11010)_2\)。
把得到的 \((11010)_2\) 最後移動的 \(1\) 原先的位置一直到最低位的所有 \(1\) 都移到最右邊。這裏最後移動的 \(1\) 原來在第三位，所以最後三位 \(010\) 要變成 \(001\)，得到 \((11001)_2\)。

這個過程可以用位運算優化：

int t = x + (x & -x);
x = t | ((((t&-t)/(x&-x))>>1)-1);

第一個步驟中，我們把數 \(x\) 加上它的 lowbit，在二進制表示下，就相當於把 \(x\) 最右邊的連續一段 \(1\) 換成它左邊的一個 \(1\)。如剛才提到的二進制數 \((10110)_2\)，它在加上它的 lowbit 後是 \((11000)_2\)。這其實得到了我們答案的前半部分。
我們接下來要把答案後面的 \(1\) 補齊，\(t\) 的 lowbit 是 \(x\) 最右邊連續一段 \(1\) 最左邊的 \(1\) 移動後的位置，而 \(x\) 的 lowbit 則是 \(x\) 最右邊連續一段 \(1\) 最左邊的位置。還是以 \((10110)_2\) 為例，\(t = (11000)_2\)，\(\operatorname{lowbit}(t) = (01000)_2\)，\(\operatorname{lowbit}(x)=(00010)_2\)。
接下來的除法操作是這種位運算中最難理解的部分，但也是最關鍵的部分。我們設原數最右邊連續一段 \(1\) 最高位的 \(1\) 在第 \(r\) 位上（位數從 \(0\) 開始），最低位的 \(1\) 在第 \(l\) 位，\(t\) 的 lowbit 等於 1 << (r+1) ，\(x\) 的 lowbit 等於 1 << l， (((t&-t)/(x&-x))>>1) 得到的，就是 (1<<(r+1))/(1<<l)/2 = (1<<r)/(1<<l) = 1<<(r-l) ，在二進制表示下就是 \(1\) 後面跟上 \(r-l\) 個零，零的個數正好等於連續 \(1\) 的個數減去 \(1\) 。舉我們剛才的數為例，\(\frac{\operatorname{lowbit(t)/2}}{\operatorname{lowbit(x)}} = \frac{(00100)_2}{(00010)_2} = (00010)_2\) 。把這個數減去 \(1\) 得到的就是我們要補全的低位，或上原來的數就可以得到答案。

所以枚舉 \(0\sim n\) 按漢明權重遞增的排列的完整代碼為：

for (int i = 0; (1<<i)-1 <= n; i++) {
    for (int x = (1<<i)-1, t; x <= n; t = x+(x&-x), x = x ? (t|((((t&-t)/(x&-x))>>1)-1)) : (n+1)) {
        // 寫下需要完成的操作
    }
}

其中要注意 \(0\) 的特判，因為 \(0\) 沒有相同漢明權重的後繼。

內建函數

GCC 中還有一些用於位運算的內建函數：

int __builtin_ffs(int x) ：返回 \(x\) 的二進制末尾最後一個 \(1\) 的位置，位置的編號從 \(1\) 開始（最低位編號為 \(1\) ）。當 \(x\) 為 \(0\) 時返回 \(0\) 。
int __builtin_clz(unsigned int x) ：返回 \(x\) 的二進制的前導 \(0\) 的個數。當 \(x\) 為 \(0\) 時，結果未定義。
int __builtin_ctz(unsigned int x) ：返回 \(x\) 的二進制末尾連續 \(0\) 的個數。當 \(x\) 為 \(0\) 時，結果未定義。
int __builtin_clrsb(int x) ：當 \(x\) 的符號位為 \(0\) 時返回 \(x\) 的二進制的前導 \(0\) 的個數減一，否則返回 \(x\) 的二進制的前導 \(1\) 的個數減一。
int __builtin_popcount(unsigned int x) ：返回 \(x\) 的二進制中 \(1\) 的個數。
int __builtin_parity(unsigned int x) ：判斷 \(x\) 的二進制中 \(1\) 的個數的奇偶性。

這些函數都可以在函數名末尾添加 l 或 ll （如 __builtin_popcountll ）來使參數類型變為 ( unsigned ) long 或 ( unsigned ) long long （返回值仍然是 int 類型）。例如，我們有時候希望求出一個數以二為底的對數，如果不考慮 0 的特殊情況，就相當於這個數二進制的位數 -1 ，而一個數 n 的二進制表示的位數可以使用 32-__builtin_clz(n) 表示，因此 31-__builtin_clz(n) 就可以求出 n 以二為底的對數。

由於這些函數是內建函數，經過了編譯器的高度優化，運行速度十分快（有些甚至只需要一條指令）。

題目推薦

Luogu P1225 黑白棋遊戲

參考資料與註釋

位運算技巧： https://graphics.stanford.edu/~seander/bithacks.html
Other Builtins of GCC： https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

適用於 C++14 以前的標準。在 C++14 和 C++17 標準中，若原值為帶符號類型，且移位後的結果能被原類型的無符號版本容納，則將該結果轉換為相應的帶符號值，否則行為未定義。在 C++20 標準中，規定了無論是帶符號數還是無符號數，左移均直接捨棄移出結果類型的位。 ↩
適用於 C++20 以前的標準。 ↩
這種右移方式稱為算術右移。在 C++20 以前的標準中，並沒有規定帶符號數右移運算的實現方式，大多數平台均採用算術右移。在 C++20 標準中，規定了帶符號數右移運算是算術右移。 ↩
一個數二進制表示從低往高的第一個 \(1\) 連同後面的零，如 \((1010)_2\) 的 lowbit 是 \((0010)_2\)，詳見樹狀數組。 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

位運算

與、或、異或

取反

左移和右移

複合賦值位運算符

關於優先級

位運算的應用

有關 2 的冪的應用

取絕對值

取兩個數的最大/最小值

判斷兩非零數符號是否相同

交換兩個數

操作一個數的二進制位

漢明權重

構造漢明權重遞增的排列

內建函數

更多位數

題目推薦

參考資料與註釋