位运算
位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。
基本的位运算共 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。
为了方便叙述，下文中省略“按位”。
与、或、异或¶
这三者都是两数间的运算，因此在这里一起讲解。
它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。
| 运算 | 运算符 | 数学符号表示 | 解释 |
|---|---|---|---|
| 与 | & | 、 | 只有两个对应位都为 时才为 |
| 或 | | | 、 | 只要两个对应位中有一个 时就为 |
| 异或 | ^ | 、 | 只有两个对应位不同时才为 |
注意区分逻辑与（对应的数学符号为 ）和按位与、逻辑或（）和按位或的区别。网络中的资料中使用的符号多有不规范之处，以上下文为准。
异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 。
举例：
取反¶
取反是对一个数 进行的位运算，即单目运算。
取反暂无默认的数学符号表示，其对应的运算符为 ~。它的作用是把 的二进制补码中的 和 全部取反（ 变为 ， 变为 ）。有符号整数的符号位在 ~ 运算中同样会取反。
补码：在二进制表示下，正数和 的补码为其本身，负数的补码是将其对应正数按位取反后加一。
举例（有符号整数）：
左移和右移¶
num << i 表示将 的二进制表示向左移动 位所得的值。
num >> i 表示将 的二进制表示向右移动 位所得的值。
举例：
移位运算中如果出现如下情况，则其行为未定义：
- 右操作数（即移位数）为负值；
- 右操作数大于等于左操作数的位数；
例如，对于 int 类型的变量 a ， a<<-1 和 a<<32 都是未定义的。
对于左移操作，需要确保移位后的结果能被原数的类型容纳，否则行为也是未定义的。1对一个负数执行左移操作也未定义。2
对于右移操作，右侧多余的位将会被舍弃，而左侧较为复杂：对于无符号数，会在左侧补 ；而对于有符号数，则会用最高位的数（其实就是符号位，非负数为 ，负数为 ）补齐。3
复合赋值位运算符¶
和 += , -= 等运算符类似，位运算也有复合赋值运算符： &= , |= , ^= , <<= , >>= 。（取反是单目运算，所以没有。）
关于优先级¶
位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符（详见 运算页面 ），所以使用时需多加注意，在必要时添加括号。
位运算的应用¶
位运算一般有三种作用：
-
高效地进行某些运算，代替其它低效的方式。
-
表示集合。（常用于 状压 DP 。）
-
题目本来就要求进行位运算。
需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。（但像“乘 2 的非负整数次幂”和“除以 2 的非负整数次幂”就最好使用位运算，因为此时使用位运算可以优化复杂度。）
有关 2 的幂的应用¶
由于位运算针对的是变量的二进制位，因此可以推广出许多与 2 的整数次幂有关的应用。
将一个数乘（除） 2 的非负整数次幂：
1 2 3 4 5 6 7 | // C++ Version
int mulPowerOfTwo(int n, int m) { // 计算 n*(2^m)
return n << m;
}
int divPowerOfTwo(int n, int m) { // 计算 n/(2^m)
return n >> m;
}
|
1 2 3 4 5 | # Python Version
def mulPowerOfTwo(n, m): # 计算 n*(2^m)
return n << m
def divPowerOfTwo(n, m): # 计算 n/(2^m)
return n >> m
|
Warning
我们平常写的除法是向 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 时两种方法等价，当数小于 时会有区别，如： -1 / 2 的值为 ，而 -1 >> 1 的值为 。
判断一个数是不是 的非负整数次幂：
1 2 | // C++ Version
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
|
1 2 3 | # Python Version
def isPowerOfTwo(n):
return n > 0 and (n & (n - 1)) == 0
|
对 的非负整数次幂取模：
1 2 | // C++ Version
int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }
|
1 2 3 | # Python Version
def modPowerOfTwo(x, mod):
return x & (mod - 1)
|
取绝对值¶
在某些机器上，效率比 n > 0 ? n : -n 高。
1 2 3 4 5 6 7 8 | // C++ Version
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 就是绝对值 */
}
|
1 2 3 4 5 6 7 8 9 | # Python Version
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 高。
1 2 3 4 | // C++ Version
// 如果 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); }
|
1 2 3 4 5 6 | # Python Version
# 如果 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)
|
判断两非零数符号是否相同¶
1 2 3 4 | // C++ Version
bool isSameSign(int x, int y) { // 有 0 的情况例外
return (x ^ y) >= 0;
}
|
1 2 3 4 | # Python Version
# 有 0 的情况例外
def isSameSign(x, y):
return (x ^ y) >= 0
|
交换两个数¶
该方法具有局限性
这种方式只能用来交换两个整数，使用范围有限。
对于一般情况下的交换操作，推荐直接调用 algorithm 库中的 std::swap 函数。
1 | void swap(int &a, int &b) { a ^= b ^= a ^= b; }
|
操作一个数的二进制位¶
获取一个数二进制的某一位：
1 2 3 | // C++ Version
// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) { return (a >> b) & 1; }
|
1 2 3 4 | # Python Version
# 获取 a 的第 b 位，最低位编号为 0
def getBit(a, b):
return (a >> b) & 1
|
将一个数二进制的某一位设置为 ：
1 2 3 | // C++ Version
// 将 a 的第 b 位设置为 0 ，最低位编号为 0
int unsetBit(int a, int b) { return a & ~(1 << b); }
|
1 2 3 4 | # Python Version
# 将 a 的第 b 位设置为 0 ，最低位编号为 0
def unsetBit(a, b):
return a & ~(1 << b)
|
将一个数二进制的某一位设置为 ：
1 2 3 | // C++ Version
// 将 a 的第 b 位设置为 1 ，最低位编号为 0
int setBit(int a, int b) { return a | (1 << b); }
|
1 2 3 4 | # Python Version
# 将 a 的第 b 位设置为 1 ，最低位编号为 0
def setBit(a, b):
return a | (1 << b)
|
将一个数二进制的某一位取反：
1 2 3 | // C++ Version
// 将 a 的第 b 位取反 ，最低位编号为 0
int flapBit(int a, int b) { return a ^ (1 << b); }
|
1 2 3 4 | # Python Version
# 将 a 的第 b 位取反 ，最低位编号为 0
def flapBit(a, b):
return a ^ (1 << b)
|
这些操作相当于将一个 位整型变量当作一个长度为 的布尔数组。
模拟集合操作¶
一个数的二进制表示可以看作是一个集合（ 表示不在集合中， 表示在集合中）。比如集合 ，可以表示成 。而对应的位运算也就可以看作是对集合进行的操作。
| 操作 | 集合表示 | 位运算语句 |
|---|---|---|
| 交集 | a & b | |
| 并集 | a|b | |
| 补集 | ~a （全集为二进制都是 1） | |
| 差集 | a & (~b) | |
| 对称差 | a ^ b |
子集遍历：
1 2 3 4 | // 遍历 u 的非空子集
for (int s = u; s; s = (s - 1) & u) {
// s 是 u 的一个非空子集
}
|
用这种方法可以在 （ 表示 二进制中 1 的个数）的时间复杂度内遍历 的子集，进而可以在 的时间复杂度内遍历大小为 的集合的每个子集的子集。（复杂度为 是因为每个元素都有 不在大子集中/只在大子集中/同时在大小子集中 三种状态。）
内建函数¶
GCC 中还有一些用于位运算的内建函数：
-
int __builtin_ffs(int x)：返回 的二进制末尾最后一个 的位置，位置的编号从 开始（最低位编号为 ）。当 为 时返回 。 -
int __builtin_clz(unsigned int x)：返回 的二进制的前导 的个数。当 为 时，结果未定义。 -
int __builtin_ctz(unsigned int x)：返回 的二进制末尾连续 的个数。当 为 时，结果未定义。 -
int __builtin_clrsb(int x)：当 的符号位为 时返回 的二进制的前导 的个数减一，否则返回 的二进制的前导 的个数减一。 -
int __builtin_popcount(unsigned int x)：返回 的二进制中 的个数。 -
int __builtin_parity(unsigned int x)：判断 的二进制中 的个数的奇偶性。
这些函数都可以在函数名末尾添加 l 或 ll （如 __builtin_popcountll ）来使参数类型变为 ( unsigned ) long 或 ( unsigned ) long long （返回值仍然是 int 类型）。 例如，我们有时候希望求出一个数以二为底的对数，如果不考虑 0 的特殊情况，就相当于这个数二进制的位数 -1 ，而一个数 n 的二进制表示的位数可以使用 32-__builtin_clz(n) 表示，因此 31-__builtin_clz(n) 就可以求出 n 以二为底的对数。
由于这些函数是内建函数，经过了编译器的高度优化，运行速度十分快（有些甚至只需要一条指令）。
更多位数¶
如果需要操作的集合非常大，可以使用 bitset 。
题目推荐¶
参考资料与注释¶
- 位运算技巧： https://graphics.stanford.edu/~seander/bithacks.html
- Other Builtins of GCC： https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用