位运算

Izudia大约 5 分钟

位运算指的是对二进制数的位进行操作的运算。

常见的位运算符包括：

运算符	描述
&	按位与，两个相应位都为 1 时，结果为 1；否则为 0。用于清零某些位数。
\|	按位或，两个相应位都为 0 时，结果为 0；否则为 1。用于设定某些位数。
~	按位取反，对每个二进制位取反，即 0 变成 1，1 变成 0。用于二进制数的补码运算。
^	按位异或，两个相应位不相同则为 1，否则为 0。用于两个二进制数间的差异比较或变换。
<<	左移运算，把位数左移 n 位，右边用 0 填充。相当于乘以 2 的 n 次方。用于二进制数的位数变换。
>>	右移运算，把位数右移 n 位，左边用符号位补充。相当于除以 2 的 n 次方。用于二进制数的位数变换。

位运算常被用来优化程序、图像处理、密码学等领域中的算法。

补码

补码是一种计算机表示有符号整数的方式，它是二进制补充原理的应用。在计算机中，一个有符号整数通常用一个固定长度的二进制数字来表示，补码就是用来表示这种有符号整数的。

在一个固定长度的二进制数字中，用最高位来表示符号位，0表示正数，1表示负数。正数的补码就是其本身，而负数的补码则需要通过一定的转换规则得到。具体来说，对于一个负数，它的补码等于它的绝对值的二进制表示的反码加1。

例如，对于一个8位二进制数-7，它的绝对值的二进制表示为00000111，反码为11111000，再加1就得到了它的补码11111001。同样的，对于一个8位二进制数7，它的补码就是00000111。

补码的优点在于可以用相同的运算方式处理有符号整数和无符号整数，同时减法也可以通过加上一个数的补码来实现，避免了硬件复杂度的提升。

移位运算是指将一个二进制数的所有位向左或向右移动一定数量的位数的运算。在计算机中，移位运算通常用于对二进制数进行数值的扩大或缩小、位的提取或填充等操作。

常见的移位运算符有：

数学上，左移相当于将原数乘以一个2的幂次方，右移则相当于将原数除以一个2的幂次方。因此，在计算机中，移位运算也经常用来优化程序，特别是对于2的幂次方等数值的操作。

二进制状态压缩是一种常见的算法技巧，常用于对大量状态或情况的处理，可以将一个大规模的状态集合压缩成一个简单的二进制数字。通过对二进制数字进行位运算，可以快速地处理和查询状态集合的信息，从而达到优化算法效率的目的。

常见的场景包括图论中的最短路问题、搜索算法中的状态记录等。通常采用整型数组来记录状态集合，其中每个元素对应一个二进制数，每个二进制位表示一个状态是否存在。例如对于一个有8种状态的问题，可以用一个8位的二进制数来表示状态集合，其中第i位为1表示第i种状态存在，为0表示不存在。

通过二进制状态压缩，可以大大减小状态集合的存储空间和处理时间，提高程序效率和性能。但需要注意的是，由于二进制状态压缩采用的是位运算，最终结果可能会受到位数限制导致的误差或溢出问题的影响，需要在具体应用场景中进行详细的分析和处理。

当n为偶数时，n xor 1 等于 n + 1；

当n为奇数时，n xor 1 等于 n - 1。

这一性质常用于图论邻接表中的边集存储。在具有无向边的图中把一堆正反方向的边分别存储在邻接表的第n、第n+1位置上，可以通过成对变换来快速地判断一条边的正反方向。

lowbit(n)定义为非负整数n在二进制表示下，保留最低位的1及其后边全部的0所构成的数值。例如，对于二进制数10100，它的lowbit运算结果为100。

$$lowbit(n) = n & (\sim n + 1) = n & (-n)$$

lowbit运算配合Hash可以找出整数二进制表示下所有时1的位置。

lowbit运算也常用于树状数组中。