【位运算】位运算常见公式总结

1、基础位运算

​ 常见的位运算就是 >>、<<、~、&、|、^，这里主要讲的是后三者！

• &：有 0 就是 0。
• |：有 1 就是 1。
• ^：相同为 0，相异为 1，或者也可以进行无进位相加，如下图所示：

2、给一个数 n，确定它的二进制表示中的第 x 位是 0 还是 1

​ 我们首先规定，包括下面的所有题，都是从右往左，从下标 0 开始增大计算。

​ 这道题是比较简单的，想要判断是 1 还是 0，那么我们 就让该位置 & 上 1 即可，如果 & 完得到 1 的话那就是 1，0 的话就是 0，而其它位置我们也不需要去考虑什么情况，直接 让 (n >> x) & 1 即可！

3、将一个数 n 的二进制表示的第 x 位修改成 1

​ (1 << x) | n 得到的就是结果！

4、将一个数 n 的二进制表示的第 x 位修改成 0

​ ~(1 << x) & n 得到的就是结果！

💥5、提取一个数 n 二进制表示中最右侧的 1

​ 这种问题叫做 lowbit 问题，其实就是一个套路，是固定的！这个套路就是 n & -n。

​ 因为 -n 其实就是 n 的取反后加一，也就是说 -n 相当于将最右侧的 1 左边的区域全都变成相反，如下所示：

​ 会得到一个规律，就是最右侧的那个 1 的左边的二进制数都是相反的，而其右边都是 0，所以我们只要让 n & -n 就能获得最右侧的 1 了！

💥6、干掉一个数 n 二进制表示中的最右侧的 1

​ 这个也是一个套路，就是 n & (n - 1)，这个 n-1 其实本质就是将最右侧的 1 右边的区域包括这个最右侧的 1 全都变成相反，所以和 n 与上之后就得到了这个结果，如下所示：

💥7、异或^的运算律

• a ^ 0 = a
• a ^ a = 0（相当于是一个消消乐）
• a ^ b ^ c = a ^ (b ^ c)