对二进制中的每一位进行逻辑操作，而不考虑整个数的数值大小
与位运算有关的特殊数据结构如[[树状数组]]或[[01线性基]]
一般对正整数进行运算
几种位运算
按位与AND &
只有两个位都为1时，结果才为1，否则为0。
两个数字做与运算，结果不会变大。
做如下变换：
| 1 | 0 | 0 | 1 | 9 |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 13 |
| 1 | 0 | 0 | 1 | 与运算结果 |
按位或OR |
只要两个位中有一个为1，结果就为1，否则为0。
两个数字做或运算，结果不会变小。
做如下变换：
| 1 | 0 | 0 | 1 | 9 |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 13 |
| 1 | 1 | 0 | 1 | 或运算结果 |
按位异或XOR ^
当两个位不同时，结果位为1，否则为0。
两个数做异或运算，可能变大，也可能变小，也可能不变。
异或不会改变最大位宽，即高位全是0
交换律：x^y = y^x
结合律：x^(y^z) = (x^y)^z
自反性：x^x = 0
零元素：x^0 = x
逆运算：x^y = z，则有z^y = x（同时异或y，抵消掉，即自反性）
| 1 | 0 | 0 | 1 | 9 |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 13 |
| 0 | 0 | 1 | 0 | 异或运算结果 |
按位取反 ~
对操作数的每一位进行取反操作，即将0变1，将1变0。
通常用于无符号整数unsigned int，避免符号位取反造成干扰。
假设只有4位
| 0 | 0 | 0 | 1 | 1 |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 按位取反结果 |
长度不同，结果不同。
按位左移 <<
表示将一个数的二进制向左移动指定的位数。移动后低位补0。
1会移动到符号位上，所以要么使用无符号整型，要么注意不要移动到符号位。
| 0 | 0 | 0 | 1 | 1 |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 按位左移3结果（9 << 3） |
左移相当于对原数进行乘以2的幂次方的操作。
例如5 << 3 = 5(23)
按位右移 >>
将一个操作右移
高位补0，符号位有1不会移走，这是负数位移规则。右移相当于除以2的幂次方向下取整。
负数高位会保留1。
| 1 | 1 | 0 | 1 | 13 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 按位右移2结果（13 >> 2） |
相当于13/4向下取整。
位运算技巧
判断数字奇偶
公式：x & 1;
结果为1说明是奇数，结果为0说明是偶数。
与1做与运算，高位全为0，个位为1，如果x个位也为1，与运算结果为1，x是奇数；如果x个位为0，与运算结果为0，x是偶数。
获取二进制数的某一位
公式：x >> i & 1;
结果必然为0或1，表示x的二进制表示中的第i位。
修改二进制中的某一位为1或0
公式：x | (1 << i);
将x的第i位或上1，则x[i]变为1，其他位上没有影响。
x的i位是0或1，i位或上1，一定为1。
修改为0类似用与运算，就是构造出只有第i位为0，其他位都为1的数然后做与运算。公式：x & ~(1 << i);
快速判断一个数是否为2的幂次方
公式：x & (x - 1);
如果x为2的幂次方，则x的二进制表示中只有1个，x - 1就有很多个连续的1并且和x的1没有交集，两者与运算一定为0，可证明其他情况必然不为0。
获取二进制位中最低位的1
公式：lowbit(x) = x & -x;
如果x = (010010)，则lowbit(x) = (000010)
常用于数据结构[[树状数组]]中。