Swift学习18：运算符应用举例

两个数字交换

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

var a  = 1
var b = 2
a = a ^ b
b = a ^ b
a = a ^ b
print(a)
print(b)

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

• 给定一个无符号整型 UInt 变量，求其二进制表中 1 的个数，要求算法执行效率尽可能的高

思路：看一个八位整数 10 100 001 ，先判断最后一位是否为 1 ，而 与 操作可以达到目前。可以把这个 八位数字 与 00 0000 01 进行 与 操作，如果结果为 1，则表示当前八位数的最后一位为 1，否则为 0 。怎么判断第 二 位呢？向右移位，再延续前面的判断即可

// 有几个 1
func countsOfOnes(num:UInt) -> UInt {
    var count:UInt = 0
    var temp = num
    while temp != 0 {
        // 如果都是位 1 才累加
        count += temp & 1
        // 右移
        temp = temp >> 1
    }
    return count
}
countsOfOnes(num: 8)

• 如果整数的二进制中有较多的 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，然后继续上面的操作

计数器 count = 0

步骤一：整数不为0，说明二进制里面肯定有1，count = 1

11 000 000 & 10 111 111 = 10 000 000 (消去第7位的1)

步骤二：结果不为 0，说明二进制里还有 1，count = 2

10 000 000 & 01 111 111 = 0（消去第8位的1）

func countsOfOnes2(num:UInt) -> UInt {
    var count:UInt = 0
    var temp = num
    while temp != 0 {
        count += 1
        temp = temp & (temp - 1)
    }
    return count
}
countsOfOnes2(num: 3)

引申：如果判断一个征收为2的整数次幂

• 给定一个无符号整型 UInt 变量，判断是否为 2 的整数次幂

• 思路：一个整数如果是 2 的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是 0，根据前面的分析，把这个整数减去 1 后再和它自己做 & 运算，这个整数中唯一的 1 就变成 0 了，也就是得到的结果是 0

// 2的整数次幂
func isPowerTwo(num:UInt) -> Bool {
    return (num & (num - 1)) == 0
}
isPowerTwo(num: 18)

缺失的数字

• 很多成对出现的正整数保存在磁盘文件中，注意成对数字不一定是相邻的，如果 2、3、4、3、4、2、..，由于意外有一个数字消失了，如何尽快找到是哪个数字消失了？

思路：考虑 ^ 异或操作的定义，当两个操作的数对应位不相同时，改数的对应位就为1。也就是说如果是相等的两个数 ^异或，得到的结果就是 0，而 0 与任何数字 ^异或，得到的是那个数字本身。所以我们考虑将所有的数字做 ^异或操作，因为只有一个数字消失，那么其他俩俩出现的数字 ^异或后为0，0与仅有的一个的数字做 ^异或，我们就得到了消失的数字是哪个？

// 缺失的数字
func findLostNum(nums:[UInt]) -> UInt {
    var lostNum:UInt = 0
    for num in nums {
        lostNum = lostNum ^ num
    }
    return lostNum
}
findLostNum(nums: [1,3,2,4,2,1,3])

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

思路：
假设题目中这两个只出现1次的数字分别是A和B，如果能将A，B分开到二个数组中，那显然符合 异或 解法的关键点了，因此这个题目的关键点事将A和B分开到二个数组中。
由于A，B肯定是不相等的，因此在二进制上肯定有一位是不同的。根据这一位是 0 还是 1 可以将A和B分开到A组合B组。
而这个数组中其它数字那么就属于A组，要么就属于B组。再对A组 和 B组 分别执行 异或 解法，就可以得到A,B了。
而要判断A，B在哪一位上不相同，只要根据 A ^ B 的结果就可以知道了，这个结果在二进制上为 1 的位都说明 A，B在这一位上是不同的

// 丢失的两个不同数
func findTwoLostNum(nums:[UInt]) -> (UInt,UInt) {
    var lostNum1:UInt = 0
    var lostNum2:UInt = 0
    var temp:UInt = 0
    // 计算两个数的异或结果
    for num in nums {
        temp = temp ^ num
    }
    // 找到第一个为 1 的位
    var flag:UInt = 1
    while ((flag & temp) == 0) {
        flag = flag << 1
    }
    // 找到两个丢失的数字
    for num in nums {
        if (num & flag) == 0 {
            lostNum1 = lostNum1 ^ num
        }else {
            lostNum2 = lostNum2 ^ num
        }
    }
    return (lostNum1,lostNum2)
}
findTwoLostNum(nums: [1,2,3,4,2,1])