常见位运算总结
基础位运算符号
这六个位运算符是实现位运算算法的重要运算符,在 C 语言阶段有详细的介绍。

记法如图所示,强调一下什么是无进位相加?
异或运算的规则决定了它天然契合无进位相加的概念。异或运算在比较两个二进制位时,0 ^ 0 = 0,0 ^ 1 = 1,1 ^ 0 = 1,1 ^ 1 = 0。只是单纯对比两个数在每一位上的值,将不同的视为 1,相同的视为 0,不涉及向高位进位。
确定二进制表示中的第 x 位是 0 还是 1
约定二进制位从右到左,为最低位到最高位,定义为从 0 到 31,为的就是对应右移 x 位刚好对应第 x 位。所以将要比较的数 n 的第 x 位右移 x 位,与 1 按位与 &,如果是 0,第 x 位为 0;如果是 1,第 x 位是 1。

修改二进制表示的第 x 位
修改成 1: 要修改数 n 第 x 位为 1 就不能破坏原来的数,所以将 1 移动 x 位,与 1 按位或 |,只修改了我们想要修改的那一位。

修改成 0: 要修改数 n 第 x 位为 0 就不能破坏原来的数,所以将 1 移动 x 位,取反 ~ 为 0,与 1 按位与 &,只修改了我们想要修改的那一位。

位图的思想
位图其实和哈希表相似,哈希表是额外开辟一个空间,计算数据出现频次,而位图则是把数据存在数据类型一个个字节里,这就省去了多开一个空间,然后利用上述的方法修改为 1 或 0,统计数是否出现过。

提取最右侧的 1
将数 n 取反后 +1 得到相反数 -n,然后两数按位与 & 得到最右侧的 1。即最右侧的 1 及其右边都不变,左边的数都变成 0。

























