位运算的几种应用

例1：不借助临时变量，交换两个数的值

思路：通过异或，先求出两个变量的不同的位

var a = 10
var b = 8

a = a ^ b
b = a ^ b
a = a ^ b

例2：求一个UInt二进制数中1的个数

思路：比如一个 1011 0100 这个二进制数，先用 1(0000 0001)和它做"与"操作，如果结果为 1，说明在最右边的这一位是 1，继续把 1 左移 1 位重复比较

func getCountOfOne(num: UInt) -> UInt {
    var count: UInt = 0
    var temp = num
    var loopCount = 0
    while temp != 0 {
        count += (temp & 1)
        temp = (temp >> 1)
        loopCount += 1
    }
    print("loop1 count: \(loopCount)")
    return count
}

上述算法有一个可以优化的地方，当有这样一个数 1100 0000，如果还是从最右边往左判断的话，有大量的 0 是没有必要的，我们可以从左边开始，让 num 和 num-1 这两个数做"与"运算，如果结果为 0，则说明这个数后续已经没有 1 了，反之继续比较

func getCountOfOne2(num: UInt) -> UInt {
    var count: UInt = 0
    var temp = num
    var loopCount = 0
    while temp != 0 {
        count += 1
        temp = temp & (temp-1)
        loopCount += 1
    }
    print("loop2 count: \(loopCount)")
    return count
}

例3：判断一个UInt数是否为2的整数幂次方

思路：能成为 2 的整数次幂的数，其二进制一定是这种类型的：1000 0000，如果 1000 0000 和它的 -1 后的数 0111 1111 做"与"操作，结果就是 0

func isPowerOfTwo(num: UInt) -> Bool {
    return (num & (num-1)) == 0
}

例4：找丢失数

一堆成对出现的数：1，2，3，4，3，2，1，找出其中缺失的一个数

思路：给定一个初始值，和数组里面的所有数做"异或"操作，成对出现的数和0做完异或操作后，结果依然是0，最后缺失的那个数4和0做异或操作，结果依然是4

func findLostNum(nums: [UInt]) -> UInt {
    var lostNum: UInt = 0
    for num in nums {
        lostNum = lostNum ^ num
    }
    return lostNum
}

如果有两个数缺失呢？

思路：分两组来计算。先求他们的异或结果，然后找出可以区分缺失的两个数的最右边为1的位的flag（缺失的两个数最右侧为1的位数肯定是不一样的），遍历数组，根据num和flag的"与"运算是否为0，分为2组，分别做异或运算，这里就和上面的过程一致了。

func findTwoLostNums(nums: [UInt]) -> (UInt, UInt) {
    var num1: UInt = 0
    var num2: 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 (flag & num) == 0 {
            num1 = num1 ^ num
        } else {
            num2 = num2 ^ num
        }
    }
    return (num1, num2)
}

来自 https://leejnull.github.io/2019/09/07/2019-09-07/