二进制

https://oi-wiki.org/math/binary-set/

位操作

1. 设置位：

   • 将整数x的第n位设置为1：x |= (1 << n)

2. 清除位：

   • 将整数x的第n位设置为0：x &= ~(1 << n)

3. 切换位：

   • 切换整数x的第n位：x ^= (1 << n)

4. 检查位：

   • 检查整数x的第n位是否为1：(x & (1 << n)) != 0

5. 获取最低位的1：

   • 获取x的最低位的1：x & -x

6. 清除最低位的1：

   • 清除x的最低位的1：x & (x - 1)

7. 提取特定位：

   • 提取x的第n位到第m位：(x >> n) & ((1 << (m - n + 1)) - 1)

8. 位计数：

   • 计算x中1的数量：使用内置函数（如C++中的__builtin_popcount或Java中的Integer.bitCount），或者通过手动循环计数。

9. 奇偶校验：

   • 检查x的奇偶性：x & 1（结果为0表示偶数，为1表示奇数）

10. 符号扩展：

    • 对于一个位宽固定的有符号整数x，将其符号位扩展到更大的位宽：使用算术右移操作（如x >> n）

11. 最高/低位1的位置

    • Integer.numberOfTrailingZeros()
    • Integer.numberOfLeadingZeros()

12. 二进制反转：

    • 反转x的二进制表示：需要通过循环和位操作实现，没有直接的内置函数。

      Integer.reverse()

13. 最高位的1：

    • 找到x最高位的1：可以通过循环左移操作实现，也可以使用特定语言的内置函数（如C++中的__builtin_clz）

位操作非常适合处理二进制数、位掩码、位图等场景，也常用于优化性能，特别是在竞赛编程、系统编程、加密算法等领域。由于直接操作位，位操作通常比基于数值的操作更快

集合操作

一个数的二进制表示可以看作是一个集合（ 表示不在集合中， 表示在集合中）。比如集合 ，可以表示成 。而对应的位运算也就可以看作是对集合进行的操作。

操作	集合表示	位运算语句
交集	$a \cap b$	a & b
并集	$a \cup b$	`a
补集	$\bar{a}$	~a （全集为二进制都是 1）
差集	$a \setminus b$	a & (~b)
对称差	$a\triangle b$	a ^ b

在进一步介绍集合的子集遍历操作之前，先看位运算的有关应用例子。

子集遍历

遍历一个二进制数表示的集合的全部子集，等价于枚举二进制数对应掩码的所有子掩码。

掩码是一串二进制码，用于和源码进行与运算，得到屏蔽源码的若干输入位后的新操作数。

掩码对于源码可以起到遮罩的作用，掩码中的 1 位意味着源码的相应位得到保留，掩码中的 0 位意味着源码的相应位进行置 0 操作。将掩码的若干 1 位改为 0 位可以得到掩码的子掩码，掩码本身也是自己的子掩码。

给定一个掩码 m，希望有效z迭代 m 的所有子掩码 s，可以考虑基于位运算技巧的实现。

// 降序遍历 m 的非空子集
for (int s = m; s != 0; s = (s - 1) & m)
// s 是 m 的一个非空子集

遍历所有掩码的子掩码

在状压DP中非常常用

for (int m = 0; m < (1 << n); m++) {
    // 降序遍历 m 的非空子集
	for (int s = m; s != 0; s = (s - 1) & m)
	// s 是 m 的一个非空子集
}

时间复杂度O3n

上面的做法算作查表法，意思是用其它状态更新当前状态。但是这种写法无法跳过无效的状态，在很多不必要的计算上浪费了大量时间。