位运算符应用举例

位运算在 LeetCode 上有一些练习题，没想到 张杰 老师在讲 Swift 的同时，还会举几个例子。这几个例子虽然我都能做出来，但是却没有张杰老师的思路那么好，就是说代码的运行效率比老师介绍的要差许多。我觉得学这么久 Swift，都没有这几道练习题这么有价值。

两个数字交换

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

// 两个数字的交换
var a = 10
var b = 8
a = a ^ b
b = a ^ b
a = a ^ b
print("a is \(a)")
print("b is \(b)")

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

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

func countOfOnes(num: UInt) -> UInt {
    var count: UInt = 0
    var temp = num

    while temp != 0 {
        count += (temp & 1)
        temp = temp >> 1
    }
    
    return count
}
// 输出 5
print(countOfOnes(num: 0x1110110))

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

1. 计数器 count = 0
2. 步骤一：整数不为 0，说明二进制里肯定有 1，count = 1
   11 000 000 & 10 111 111 = 10 000 000 消去第 7 位的 1
3. 步骤二：结果不为 0，说明二进制里还有 1，count = 2
   10 000 000 & 01 111 111 = 0 消去第 8 位的 1
4. 步骤三：结果为 0，终止，返回 count 为 2

func countOfOnes2(num: UInt) -> UInt {
    var count: UInt = 0
    var temp = num

    while temp != 0 {
        count += 1
        temp = temp & (temp - 1)
    }

    return count
}
// 输出 5
print(countOfOnes2(num: 0x1110110))

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

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

func isPowerOfTwo(num: UInt) -> Bool {
    return (num & (num - 1)) == 0
}
// 输出 true
print(isPowerOfTwo(num: 4))
// 输出 false
print(isPowerOfTwo(num: 6))
// 输出 false
print(isPowerOfTwo(num: 9))

---

我的微信公众号：“码农UP2U”