位运算

---

计算机中的数在内存中都是以二进制形式进行存储的 ，位运算是将每个二进制位作为 布尔值，分别对一个或两个二进制数中对应的二进制位做布尔运算。

注意：在手动进行 位运算计算 时，需要将数转换成二进制的表示形式，再进行计算。如: 3 & 5，先写成二进制形式的 0011 和 0101，右边最低位对齐后再分别对相应位进行位运算。

位运算规则介绍

---

位运算常用性质

---

【简单规则】

（1）x 与自身之间的操作

x & x = x;
x | x = x;
x ^ x = x;

（2）x 与 0 之间的操作

x & 0 = 0;
x | 0 = x;
x ^ 0 = x;

（3）还原计算

x | ( x & y ) = x;
x & ( x | y ) = x;

【基础性质】

“清零取反要用 与 ，某位置一可用 或 。若要取反和交换，轻轻松松用 异或 ”

（4）判断奇偶

// 通过 & 1 取出最后一个二进制位以达到模 2 的效果，位运算效率更高
if(x & 1 == 1) // 奇数
if(x & 1 == 0) // 偶数
// 等价(x % 2)

（5）比较两个整数是否相等

x ^ y // 如果结果为0则为相等，反之不等

（6）正整数 乘 或 除以 $2^n$

x  = x << n; // 乘以 2^n；
x  = x >> n; // 除以 2^n；

（7）交换两个整数

x ^= y;
y ^= x;
x ^= y;

【高阶延展】

（8）取出 x 中倒数第 i 个二进制位上的数值

x & (1 << (i - 1)); 或 (x >> (i - 1)) & 1 

（9）计算 x 的相反数

x = ~x + 1; // 数字取反后等于其相反数-1

（10）保留 x 在二进制位中最后一个 1

x &= (-x); // 获取最低位位权，常用在lowbit()函数中

（11）删除 x 二进制序列中最后一个值为 1 的位置

x &= (x - 1); // 如果结果为 0，则说明 x 是 2 的指数

（12）将 x 的倒数第 i 位二进制位设为 1

x |= 1 << （i - 1）;

（12）将 x 的倒数第 i 位二进制位设为 1

x |= 1 << （i - 1）;

（13）将 x 的倒数第 i 位二进制位设为 0

x &= ~(1 << （i - 1）));

（14）保留 x 二进制序列中最后的 i 位，其余补 0

x &= ((1 << i) - 1);

（15）将 x 二进制序列中最后 i 位全部置为 0

x &= ~((1 << i) - 1)

（16）求 x 取模 $2^n$ 后的结果

x = x & ((2 ^ n) − 1); 同 x %= 2 ^ n

运算符优先级

---