算法练习：位运算和数学问题(Bit Manipulation & Math)

[ShannonChenCHN]

题目列表

位运算

• 231. 2的幂
• 338. 比特位计数（难度中等）
• 136. 只出现一次的数字
• 剑指 Offer 56 - I. 数组中数字出现的次数（难度中等）
• 191. 位1的个数
• 461. 汉明距离
• 190. 颠倒二进制位
• 268. 丢失的数字
• 51. N 皇后（难度困难）
• 剑指 Offer 65. 不用加减乘除做加法

数学问题

• 7. 整数反转
• 9. 回文数
• 326. 3的幂
• 204. 计数质数
• 29. 两数相除
• 633. 平方数之和

总结

1. 把一些常用的位运算特点背下来
   • 与 &，或 |，非 ~，异或 ^，左移 <<，右移 >>
   • (x & 1) == 1 等价于 (x % 2 == 1)
   • (x & 1) == 0 等价于 (x % 2 == 0)
   • x / 2 等价于 x >> 1
   • x &= (x - 1) 把x最低位的二进制1给去掉
   • x & -x 只保留最低位的1，而把其他位的1都去掉
   • x & ~x 得到 0
2. 异或运算也是一个考点
   • x^0 = x
   • x ^ x = 0

[ShannonChenCHN]

理论知识

一、位运算

1. 什么是位运算？

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）：

110
AND 1011
———-
0010 –  2

由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

2. 常用位运算操作（重点掌握）

判断奇偶：

(x & 1) == 1 等价于 (x % 2 == 1) ⭐️
(x & 1) == 0 等价于 (x % 2 == 0) ⭐️

x / 2 等价于 x >> 1 ⭐️
x &= (x - 1) 把x最低位的二进制1给去掉 ⭐️
x & -x 只保留最低位的1，而把其他位的1都去掉 ⭐️
x & ~x 得到 0 ⭐️

3. 指定位置的位运算

将X最右边的n位清零：x & (~0 << n)
获取x的第n位值：(x >> n) & 1
获取x的第n位的幂值：x & (1 << n)
仅将第n位置为1：x | (1 << n)
仅将第n位置为0：x & (~(1 << n))
将x最高位至第n位（含）清零：x & ((1 << n) - 1)
将第n位至第0位（含）清零：x & (~((1 << (n + 1)) - 1))

4. 异或操作的特点

x^0 = x ⭐️
x ^ 1s = ~x （注：1s = ~0）
x ^ (~x) = 1s
x ^ x = 0 ⭐️

交换律：

a ^ b ^ c = a ^ (b ^ c) = (a ^ c) ^ b

不使用其他空间，交换两个值：

a = a ^ b;
b = a ^ b; //a ^ b ^ b = a ^ 0 = a;
a = a ^ b;

参考

• 你应该背下的位操作知识
• 极客时间专栏

[ShannonChenCHN]

231. 2的幂

2021.05.06 11:30 am ~11:59 am

参考题解：

• https://leetcode-cn.com/problems/power-of-two/solution/power-of-two-er-jin-zhi-ji-jian-by-jyd/
• https://leetcode-cn.com/problems/power-of-two/solution/2de-mi-by-leetcode/

解法一：暴力法

思路：n 除以 2，然后将结果赋值给 n，重复这个步骤，直到 n 不能被 2 整除，也就是余数不为 0，最后得到的商为 1 则说明是 2 的幂。
时间复杂度：O(logn)
空间复杂度：O(1)

class Solution {
    func isPowerOfTwo(_ n: Int) -> Bool {
        
        var n = n
        while n % 2 == 0 {
            n = n / 2
        }
        return n == 1
    }
}

解法二：将二进制中最右边的 1 变成 0

根据二进制的特点：2 的幂在二进制中的表示是开头一个 1 后面全部都是 0。所以，我们可以通过去除二进制中最右边的 1，然后再看得到的结果是不是 0。

我们可以通过 n & (n-1) 将 n 的二进制数最后一位 1 变成 0。

class Solution {
    func isPowerOfTwo(_ n: Int) -> Bool {
        return n > 0 && (n & (n-1) == 0)
    }
}

时间复杂度：O(1)
空间复杂度：O(1)

[ShannonChenCHN]

338. 比特位计数（难度中等）

2021.05.06 12:00 pm ~12:30 pm

参考题解：

• https://leetcode-cn.com/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/
• https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/

解法一：逐个计算

时间复杂度：O(k*num)
空间复杂度：O(1)

解法二：动态规划

对于正整数 num，将其二进制数右移一位，得到的是 num/2。如果 num/2 的二进制数中 1 的个数是已知的，则 num 的二进制数中 1 的个数：

• num 为偶数：bits[num] = bits[num/2]
• num 为奇数：bits[num] = bits[num/2] + 1

时间复杂度：O(num)
空间复杂度：O(1)

class Solution {
    func countBits(_ num: Int) -> [Int] {
        var result: [Int] = [Int](repeating: 0, count: num+1)
        for i in 0...num {
            result[i] = result[i/2] + (i & 1)
        }
        return result
    }
}

[ShannonChenCHN]

51. N 皇后（难度困难）

[ShannonChenCHN]

191. 位1的个数

2021.05.06 10：00 am~ 10:30 am

参考题解：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode-solution-jnwf/

解法一：逐位检查

思路：题目中已经明确了”输入必须是长度为 32 的 二进制串“，所以我们可以通过循环，将 n 的第 i 位与 1<<i 进行与运算（因为 1<<i 正好只有第 32-i 位为 1）。

时间复杂度：O(k)，k 为输入的二进制串位数，所以 k=32。我们需要检查输入的二进制数的每一位，所以对于任何数一共需要 32 次循环。
空间复杂度：O(1)

class Solution {
    func hammingWeight(_ n: Int) -> Int {
        
        var count = 0
        for i in 0..<32 {
            if (n & (1 << i)) > 0 {
               count += 1 
            }
        }
        return count
    }
}

解法二：位运算优化

根据位运算特性：通过 n & (n-1) 可以把最后一位 1 变成 0，我们可以通过不断地计算 n & (n-1)，并将结果赋值给 n，直到 n 的没有 0 为止，就可以知道有多少个 1 了。

时间复杂度：最坏的情况下为 O(logn)，循环次数为 n 的二进制位中 1 的个数，最坏情况下，n 的二进制位全部为 1，此时 1 的个数为 logn。
空间复杂度：O(1)

class Solution {
    func hammingWeight(_ n: Int) -> Int {
        
        var n = n
        var count = 0
        while n > 0 {
            n &= (n - 1)
            count += 1
        }
        return count
    }
}

[ShannonChenCHN]

190. 颠倒二进制位

2021.05.06 08:30 pm~ 09:00 pm

参考题解：https://leetcode-cn.com/problems/reverse-bits/solution/dian-dao-er-jin-zhi-wei-by-leetcode-solu-yhxz/

解法一：逐位颠倒法

将 32 位的二进制串，从低位到高位，逐位提取出来放到相反的位置。

时间复杂度：O(1)
空间复杂度：O(1)

class Solution {
    func reverseBits(_ n: Int) -> Int {
        var n = n
        var result = 0
        for i in 1...32 {
            result |= (n & 1) << (32-i) // 取出第 i 位做或运算
            n = n >> 1
        }
        return result
    }
}

解法二：位运算分治

思路跟翻转二叉树差不多。

[ShannonChenCHN]

136. 只出现一次的数字

思路：基于 a^a=0 的特性

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var k: Int = 0
        for num in nums {
            k ^= num
        }
        return k
    }
}

[ShannonChenCHN]

剑指 Offer 56 - I. 数组中数字出现的次数（难度中等）

2021.05.06 09:15 pm ~ 09:55 pm

参考题解：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jie-di-qi-jiang-jie-fen-zu-wei-yun-suan-by-eddievi/

解法一：哈希表+两次循环

空间复杂度为 O(n)，不符合题目要求。

class Solution {
    func singleNumbers(_ nums: [Int]) -> [Int] {

        var map: [Int: Int] = [:]
        var result: [Int] = [Int]()
        for num in nums {
            if map[num] == nil {
                map[num] = 1
            } else {
                map[num] = map[num]! + 1
            }
        }
        for num in nums {
            if map[num] == 1 {
                result.append(num)
            }
        }

        return result
    }
}

解法二：异或

基于异或特性：

• n ^ 0 = n
• n ^ n = 0
• 交换律

思路：因为相同的数异或必为 0，而不同的数异或之后得到的二进制串中数为1的意味着原来的两个数的二进制位在该位不同。所以，我们可以先通过把所有的数一起异或运算找出一个 mask，然后再将所有的数和 mask 做与运算判断，进行分组，结果为 0 的为一组，不为 0 的是另一组。而每一组中的所有数做完异或运算后得到的就是两个唯一的数。

时间复杂度：O(1)
空间复杂度：O(1)

class Solution {
    func singleNumbers(_ nums: [Int]) -> [Int] {

        // 首先计算 mask，取异或结果最低位的 1
        var k: Int = 0
        for num in nums {
            k ^= num
        }
        var mask: Int = k & (-k)

        // 两组中，必有一部分数和mask做与运算的结果为0，另一部分和mask做与运算的结果不为0
        var a: Int = 0
        var b: Int = 0
        for num in nums {
            if num & mask == 0 {
                a ^= num
            } else {
                b ^= num
            }
        }

        return [a, b]
    }
}

[ShannonChenCHN]

461. 汉明距离

2021.05.06 10:00 pm ~ 10:10 pm

参考题解：https://leetcode-cn.com/problems/hamming-distance/solution/yi-ming-ju-chi-by-leetcode/

解法一：异或+移位计算

思路：通过异或得到的结果中包含两者不同的位，然后再统计这个结果中 1 的个数

时间复杂度：O(1)，因为最多 32 位
空间复杂度：O(1)

class Solution {
    func hammingDistance(_ x: Int, _ y: Int) -> Int {
        var distance: Int = 0
        var xor: Int = x ^ y
        while xor > 0 {
            if xor & 1 == 1 {
                distance += 1
            }
            xor >>= 1
        }
        return distance
    }
}

解法二：布赖恩·克尼根算法

在解法一的基础上进一步优化，基于可以用 a & (a - 1) 将最低位 1 变成 0 的特点，在循环时每次只考虑二进制位为 1 的步骤。

时间复杂度：O(1)。与移位方法相似，由于整数的位数恒定，因此具有恒定的时间复杂度。但是该方法需要的迭代操作更少。
空间复杂度：O(1)，与输入无关，使用恒定大小的空间。

class Solution {
    func hammingDistance(_ x: Int, _ y: Int) -> Int {
        var distance: Int = 0
        var xor: Int = x ^ y
        while xor > 0 {
            distance += 1
            xor = xor & (xor - 1) // 把最低位的 1 变成 0
        }
        return distance
    }
}

[ShannonChenCHN]

268. 丢失的数字

2021.05.06 10:15 pm ~ 10:30 pm

解法一：异或

基于异或运算的特性：a ^ a = 0，相同的数异或结果为 0，那么我们可以算上 [0...n] 那一组，如果对两组数全部进行异或运算，最后的结果就是多出来的那个数。

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        let n = nums.count
        var xor: Int = 0
        for i in 0...n {
            xor ^= i
        }

        for num in nums {
            xor ^= num
        }
        return xor
    }
}

因为 [0, n] 恰好是 nums 的下标加上 n，所以用一个循环即可：

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        let n = nums.count
        var xor: Int = n
        for i in 0..<n {
            xor ^= i
            xor ^= nums[i]
        }
        return xor
    }
}

解法二：两组求和+求和之差