12 Swift位运算举例

位运算举例 （1）

两个数字交换

• 不借助临时变量，交换两个变量的值

image-20230219212324623.png

求无符号整数二进制中1的个数

• 给定一个无符号整数（UInt）变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能的高
  • 思路：看一个八位整数10 100 001，先判断最后一位是否为1，而“与”操作可以达到目的。可以把这个八位的数字与00000001进行“与”操作。如果结果位1，则表示当前八位数的最后一位为1，否则为0。怎么判断第二位呢？向右位移，再延续前面的判断即可

image-20230219213149634.png

• 如果整数的二进制中有较多的0，那么我们每一次右移一位做判断会很浪费，怎么改进前面的算法呢？有没有办法让算法的复杂度只与“1”的个数有关？
  • 思路：为了简化这个问题，我们考虑只有高位有1的情况。例如：11 000 000，如何跳过前面低位的6个0，而直接判断第七位的1？我们可以设计11 000 000和10 111 111（也就是11 000 000 - 1）做“与”操作，消去最低位的1.如果得到的结果为0，说明我们已经找到或者消去里面最后一个1。如果不为0，那么说明我们消去了最低位的1，但是二进制中还有其他的1，我们的计数器需要加1，然后继续上面的操作

image-20230219213919657.png

引申：如何判断一个整数为2的整数次幂

• 给定一个无符号整数（UInt）变量，判断是否为2的整数次幂
  • 思路：一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0。根据前面的分析，把这个整数减去1后再和它自己做与运算，这个整数中唯一的1就变成0了，也就是得到的结果为0

image-20230219214433813.png

位运算举例 （2）

缺失的数字

• 很多成对出现的正整数保存在磁盘文件中，注意成对的数字不一定是相邻的，如2,3,4,3,4,2......，由于意外有一个数字消息了，如何尽快找到是哪个数字消失了？
  • 思路： 考虑“异或”操作的定义，当两个操作数的对应位不相同时，该数的对应位就为1.也就是说如果是相等的两个数“异或”，得到的结果为0，而0与任何数字“异或”，得到的是那个数字本身。所以我们考虑将所有的数字做“异或”操作，因为只有一个数字消失，那么其他两两出现的数字“异或”后为0,0与仅有的一个数字做“异或”，我们就得到了消失的数字是哪个。

image-20230219215609588.png

• 如果有两个数字意外丢失了（丢失的不是相等的数字），该如何找到丢失的两个数字？

image-20230219215843080.png image-20230219215953310.png

• 数组中，只有一个数出现一次，剩下的都出现三次，找出出现一次的数字。

位运算优先级和结合性

• 运算符的优先级使得一些运算符优先于其他运算符，高优先级的运算符会先被计算

• 结合性定义了具有相同优先级的运算符是如何结合（或关联）的--是与左边结合为一组，还是与右边结合为一组。可以这样理解：“它们是与左边的表达式结合的”或者“它们是与右边的表达式结合的”

• 2 + 3 % 4 * 5

image-20230219221117854.png

• 2 + 3 % 4 * 5 等价于 2 + ((3 % 4) * 5)

• Swift语言中逻辑运算符 && 和 ||是左相关的，这意味着多个逻辑运算符组合的表达式会首先计算最左边的字表达式

image-20230219221437833.png