位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

基本的位运算共 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。

为了方便叙述，下文中省略「按位」。

这三者都是两数间的运算，因此在这里一起讲解。

它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

注意区分逻辑与（对应的数学符号为 ）和按位与、逻辑或（）和按位或的区别。网络中的资料中使用的符号多有不规范之处，以上下文为准。

异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 。

举例：

取反是对一个数 进行的位运算，即单目运算。

取反暂无默认的数学符号表示，其对应的运算符为 ~。它的作用是把 的二进制补码中的 和 全部取反（ 变为 ， 变为 ）。有符号整数的符号位在 ~ 运算中同样会取反。

补码：在二进制表示下，正数和 的补码为其本身，负数的补码是将其对应正数按位取反后加一。

举例（有符号整数）：

num 表示将 的二进制表示向左移动 位所得的值。

num >> i 表示将 的二进制表示向右移动 位所得的值。

举例：

移位运算中如果出现如下情况，则其行为未定义：

例如，对于 int 类型的变量 a ， a 和 a 都是未定义的。

对于左移操作，需要确保移位后的结果能被原数的类型容纳，否则行为也是未定义的。1对一个负数执行左移操作也未定义。2

对于右移操作，右侧多余的位将会被舍弃，而左侧较为复杂：对于无符号数，会在左侧补 ；而对于有符号数，则会用最高位的数（其实就是符号位，非负数为 ，负数为 ）补齐。3

和 += , -= 等运算符类似，位运算也有复合赋值运算符： &= , |= , ^= , , >>= 。（取反是单目运算，所以没有。）

位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符（详见 运算页面 ），所以使用时需多加注意，在必要时添加括号。

位运算一般有三种作用：

高效地进行某些运算，代替其它低效的方式。

表示集合。（常用于 状压 DP 。）

题目本来就要求进行位运算。

需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。（但像「乘 2 的非负整数次幂」和「除以 2 的非负整数次幂」就最好使用位运算，因为此时使用位运算可以优化复杂度。）

由于位运算针对的是变量的二进制位，因此可以推广出许多与 2 的整数次幂有关的应用。

将一个数乘（除） 2 的非负整数次幂：

Warning

我们平常写的除法是向 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 时两种方法等价，当数小于 时会有区别，如： -1 / 2 的值为 ，而 -1 >> 1 的值为 。

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

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

这种方式只能用来交换两个整数，使用范围有限。

对于一般情况下的交换操作，推荐直接调用 algorithm 库中的 std::swap 函数。

获取一个数二进制的某一位：

将一个数二进制的某一位设置为 ：

将一个数二进制的某一位设置为 ：

将一个数二进制的某一位取反：

这些操作相当于将一个 位整型变量当作一个长度为 的布尔数组。

汉明权重是一串符号中不同于（定义在其所使用的字符集上的）零符号（zero-symbol）的个数。对于一个二进制数，它的汉明权重就等于它 的个数（即 popcount）。

求一个数的汉明权重可以循环求解：我们不断地去掉这个数在二进制下的最后一位（即右移 位），维护一个答案变量，在除的过程中根据最低位是否为 更新答案。

代码如下：

求一个数的汉明权重还可以使用 lowbit 操作：我们将这个数不断地减去它的 lowbit4，直到这个数变为 。

代码如下：

在 状压 DP 中，按照 popcount 递增的顺序枚举有时可以避免重复枚举状态。这是构造汉明权重递增的排列的一大作用。

下面我们来具体探究如何在 时间内构造汉明权重递增的排列。

我们知道，一个汉明权重为 的最小的整数为 。只要可以在常数时间构造出一个整数汉明权重相等的后继，我们就可以通过枚举汉明权重，从 开始不断寻找下一个数的方式，在 时间内构造出 的符合要求的排列。

而找出一个数 汉明权重相等的后继有这样的思路，以 为例：

把 最右边的 向左移动，如果不能移动，移动它左边的 ，以此类推，得到 。

把得到的 最后移动的 原先的位置一直到最低位的所有 都移到最右边。这里最后移动的 原来在第三位，所以最后三位 要变成 ，得到 。

这个过程可以用位运算优化：

所以枚举 按汉明权重递增的排列的完整代码为：

其中要注意 的特判，因为 没有相同汉明权重的后继。

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 。

Luogu P1225 黑白棋游戏

适用于 C++14 以前的标准。在 C++14 和 C++17 标准中，若原值为带符号类型，且移位后的结果能被原类型的无符号版本容纳，则将该结果 转换 为相应的带符号值，否则行为未定义。在 C++20 标准中，规定了无论是带符号数还是无符号数，左移均直接舍弃移出结果类型的位。 ↩

适用于 C++20 以前的标准。 ↩

这种右移方式称为算术右移。在 C++20 以前的标准中，并没有规定带符号数右移运算的实现方式，大多数平台均采用算术右移。在 C++20 标准中，规定了带符号数右移运算是算术右移。 ↩

一个数二进制表示从低往高的第一个 连同后面的零，如 的 lowbit 是 ，详见 树状数组。 ↩