【优选算法】Bit-Samurai：位运算的算法之道

文章目录

• 1.常见位运算总结
• • 1.1 基础位运算符号
  • 1.2 给一个数 n，确定它的二进制表示中的第 x 位是 0 还是 1
  • 1.3 将一个数 n 的二进制表示的第 x 位修改成 1
  • 1.4 将一个数 n 的二进制表示的第 x 位修改成 0
  • 1.5 位图的思想
  • 1.6 提取一个 n 二进制表示中最右侧的 1
  • 1.7 干掉一个数 n 二进制表示中最右侧的 1
  • 1.8 位运算的优先级
  • 1.9 异或运算符 ^ 的运算律
• 2.判定字符是否唯一
• 3.丢失的数字
• 4.两整数之和
• 5.只出现一次的数字Ⅱ
• 6.消失的两个数字
• 希望读者们多多三连支持
• 小编会继续更新
• 你们的鼓励就是我前进的动力！

本篇是优选算法之位运算算法，这是一种直接对整数在内存中的二进制位进行操作的运算，它的运算效率高，在快速幂算法，汉明重量，找出数组中唯一出现一次的数字，不使用额外变量交换两个数

1.常见位运算总结

1.1 基础位运算符号

这六个位运算符是实现位运算算法的重要运算符，在C语言阶段有详细的介绍过

传送门：关于我、重生到500年前凭借C语言改变世界科技vlog.10——进制转化&&操作符进阶

记法如图所示，强调一下什么是无进位相加？

异或运算的规则决定了它天然契合无进位相加的概念
异或运算在比较两个二进制位时，0 ^ 0 = 0，0 ^ 1 = 1 ，1 ^ 0 = 1， 1 ^ 1 = 0
只是单纯对比两个数在每一位上的值，将不同的视为 1，相同的视为 0 ，不涉及向高位进位

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

约定二进制位从右到左，为最低位到最高位，定义为从0到31，为的就是对应右移x位刚好对应第x位。所以将要比较的数 n 的第x位右移x位，与1按位与&，如果是0，第x位为0；如果是1，第x位是1

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

要修改数n第x位为1就不能破坏原来的数，所以将1移动x位，与1按位或|，只修改了我们想要修改的那一位

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

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

1.5 位图的思想

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

1.6 提取一个 n 二进制表示中最右侧的 1

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

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

将数n减1，然后两数按位与&干掉最右侧的1。即最右侧的1及其右边都变成0，左边的数都不变

1.8 位运算的优先级

通常优先级为：~ > & > ^ > |
但是记起来太麻烦了，干脆直接加括号更好

1.9 异或运算符 ^ 的运算律

这是异或运算符^常用的运算律，在题目中经常用

2.判定字符是否唯一

✏️题目描述：

✏️示例：

传送门：判定字符是否唯一

题解:

通常统计多数的字母出现次数一般想到的是哈希表，时间空间复杂度都为O(n)，这就有人问了，有没有既简单又强势的方法能够解决？有的兄弟有的，这么强势的方法有九个，都是当前蓝桥杯T0.5的强势方法，因为本题只涉及26个小写英文字母，所以可以用减少开辟空间的位图

如上述介绍位图一样，用1和0表示字母是否出现过，如果为1，就返回false；如果是0，就添加1到指定位数上，遍历完字符串后返回true，