位运算的几种应用
2020-01-08 本文已影响0人
leejnull
例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)
}
