hello，各位旅行者们，今天我们要开位运算书。信我，比森林书好肝多了(*/ω＼*)
一.什么是位运算符，为什么要学习它
在计算机科学中，二进制数是最基本的数据类型之一，位运算符是一类用于操作二进制数位的运算符（就像是+ - * /），它们直接对二进制数的位进行操作。
使用位运算符有几个好处：
二.位运算符都有哪些，功能分别是什么
-
与运算符（&）：对应位都为1时结果为1，否则为0。常用于提取指定位的信息、清零特定位等操作。
- 示例：假设我们有两个二进制数
1010 和 1100，我们可以使用与运算符来提取它们的共同位。 - 运算：
1010 & 1100 = 1000 - 解释：在这个例子中，只有在两个二进制数相应的位都为1时，结果的对应位才为1。因此，
1010 & 1100 的结果为 1000。 - 分配律：
a & (b | c) = (a & b) | (a & c) - 结合律：
(a & b) & c = a & (b & c) - 恒等律：
a & 1111...1111 = a - 零律：
a & 0000...0000 = 0
-
或运算符（|）：只要对应位中有一个为1时结果为1。常用于设置特定位为1、将多个条件合并等。
- 示例：假设我们有两个二进制数
1010 和 1100，我们可以使用或运算符来将它们的对应位中的任何一个为1的位设置为1。 - 运算：
1010 | 1100 = 1110 - 解释：在这个例子中，只要两个二进制数相应的位中有一个为1，结果的对应位就为1。因此，
1010 | 1100 的结果为 1110。 - 分配律：
a | (b & c) = (a | b) & (a | c) - 结合律：
(a | b) | c = a | (b | c) - 恒等律：
a | 0000...0000 = a - 零律：
a | 1111...1111 = 1
-
异或运算符（^）：对应位不同时结果为1。常用于二进制数据的加密、检查两个数是否相同等。
- 示例：假设我们有两个二进制数
1010 和 1100，我们可以使用异或运算符来检查它们的对应位是否相同。 - 运算：
1010 ^ 1100 = 0110 - 解释：在这个例子中，如果两个二进制数的对应位相同，则结果的对应位为0，否则为1。因此，
1010 ^ 1100 的结果为 0110。 - 分配律：
a ^ (b & c) = (a ^ b) & (a ^ c) - 结合律：
(a ^ b) ^ c = a ^ (b ^ c) - 恒等律：
a ^ 0000...0000 = a - 自反律：
a ^ a = 0
-
取反运算符（~）：将一个数的二进制数按位进行取反操作，即将所有的0变为1，将所有的1变为0。
- 示例：假设我们有一个二进制数
1010，我们可以使用取反运算符来对其进行取反操作。 - 运算：
~1010 = 0101 - 解释：在这个例子中，每个位的值被取反，即0变为1，1变为0。因此，
~1010 的结果为 0101。 - 取反律：
~a = -a - 1
-
左移运算符（<<）：将数字的位向左移动指定的位数，高位丢弃，低位补0。相当于乘以2的n次方。常用于在二进制数中进行乘法运算。
- 示例：假设我们有一个二进制数
1010，我们可以使用左移运算符来将其向左移动两位。 - 运算：
1010 << 2 = 101000 - 解释：在这个例子中，二进制数向左移动两位，高位丢弃，低位补0。因此，
1010 << 2 的结果为 101000。 - 结合律：
(a << b) << c = a << (b + c) - 恒等律：
a << 0 = a
-
右移运算符（>>）：将数字的位向右移动指定的位数，低位丢弃，高位补0或者保持符号位不变。相当于除以2的n次方。常用于在二进制数中进行除法运算。
- 示例：假设我们有一个二进制数
1010，我们可以使用右移运算符来将其向右移动一位。 - 运算：
1010 >> 1 = 0101 - 解释：在这个例子中，二进制数向右移动一位，低位丢弃，高位补0。因此，
1010 >> 1 的结果为 0101。 - 结合律：
(a >> b) >> c = a >> (b + c) - 恒等律：
a >> 0 = a
到了这里，脑子是不是快要
三.位运算符常用场景
在算法竞赛中常用的位运算知识点：
-
位操作技巧：
- 快速判断奇偶性：
if (x & 1) { /* x是奇数 */ } - 快速除以2：
x >>= 1（相当于x //= 2） - 快速乘以2：
x <<= 1（相当于x *= 2） - 判断第n位是否为1：
if (x & (1 << n)) { /* 第n位是1 */ } - 设置第n位为1：
x |= (1 << n) - 将第n位清零：
x &= ~(1 << n) - 切换第n位的状态：
x ^= (1 << n)
-
位运算与位掩码：
- 使用位运算符创建和操作位掩码，用于标记状态、标志位、选项等。
- 位掩码的常见操作包括设置、清除、切换某一位的状态等。
-
位运算与计数：
- 使用位运算统计二进制表示中1的个数（也称为"汉明权重"或"popcount"）。
- 可以利用技巧实现高效的计数算法，例如Brian Kernighan算法或分治法。
-
位运算与排列组合：
- 使用位运算生成子集、排列、组合等。
- 位运算可以方便地枚举所有可能的组合情况，例如使用位掩码进行组合的生成。
-
位运算与状态压缩：
- 在动态规划等问题中，使用状态压缩技巧将状态表示为一个整数，从而减少内存占用和加速计算过程。
在实战项目中常用的位运算知识点：
-
存储空间优化：
使用位运算技巧来优化存储空间，尤其在大规模数据处理、数据库设计等项目中，节省每一位的存储空间都能带来巨大的收益。 -
网络协议与数据传输：
在网络协议的设计和数据传输过程中，位运算常用于数据的编解码、校验和加密解密等操作。 -
硬件相关操作：
在嵌入式系统开发、驱动程序编写等项目中，位运算常用于与硬件的交互和控制，例如设置寄存器、处理传感器数据等。 -
加密与安全：
在信息安全领域，位运算常用于加密算法、哈希函数、身份验证等方面，保护数据的安全性和完整性。 -
图形图像处理：
在图形图像处理项目中，位运算常用于图像的压缩、颜色处理、像素操作等，提高图像处理效率和性能。 -
数据库设计：
在数据库设计中，位运算可以用于存储和操作大量的标志位、权限信息等，优化数据库结构和查询性能。