世间所有的相遇，都是久别重逢

LeetCode题目总结-位运算

发表于 更新于 分类于 ， 阅读次数： Disqus： Valine：
本文字数： 8.2k 阅读时长 ≈ 7 分钟

位运算(Bit Manipulation)一直是程序员面试中的一个必须准备的主题，不过现在面试中位运算出现的次数并不多，主要原因还是位运算太考察技巧了，很多时候很难在短时间内想出来，所以作为面试的题目显得有点太花时间了。

下面是本文的题目目录：

基础知识与常用技巧

基本的位运算知识：

  • 与运算（&）
1
2
3
0 & 0 = 0
1 & 1 = 1
1 & 0 = 0
  • 或运算（|）
1
2
3
0 | 0 = 0
1 | 0 = 1
1 | 1 = 1
  • 异或运算（^）
1
2
3
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 0 = 0

根据上面的知识我们可以知道：两个相同的数异或的结果为0，而0与任何一个数异或的结果为这个数。

常用技巧：

  • n & (n-1)能够消灭n中最右侧的一个1。
  • 右移：除以2；左移：乘以2。
  • 异或性质：交换律，0^a=a, a^a=0。
  • 我们可以将常用字符、数字等均转为按位运算，可以节约空间。

汉明距离(Hamming Weight)相关题目

191-位1的个数

问题描述

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1：

1
2
3
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

1
2
3
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

1
2
3
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

思路

我们遍历数字的 32 位。如果某一位是 1 ，将计数器加一。

进阶做法：我们可以把前面的算法进行优化。我们不再检查数字的每一个位，而是不断把数字最后一个 1 反转，并把答案加一。当数字变成 0 的时候，我们就知道它没有 1 的位了，此时返回答案。这里关键的想法是对于任意数字 n ，将 n 和 n - 1 做按位与运算，会把最后一个 1 的位变成 0 。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        while n != 0:
            # 将 n 和 n - 1 做按位与运算，把最后一个 1 的位变成 0，得到新的n
            n = n & (n-1)
            count += 1
        return count

461-汉明距离

题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：0 ≤ x, y < 231.

示例:

1
2
3
4
5
6
7
8
9
10
输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

思路

我们先对两个数进行异或，然后计算其中“1”的个数，即为这两个数的汉明距离。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # 异或
        a = x ^ y

        # 计算“1”的个数
        count = 0
        while a != 0:
            a = a & (a-1)
            count += 1
        
        return count

477-汉明距离总和

题目描述

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

计算一个数组中，任意两个数之间汉明距离的总和。

示例:

  • 输入: 4, 14, 2
  • 输出: 6
  • 解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
  • 答案：HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注意:

  • 数组中元素的范围为从 0到 10^9。
  • 数组的长度不超过 10^4。

思路

看到题意第一想法就是遍历数组，嵌套一个for循环遍历数组进行两两比较，但是这样时间复杂度高达O(N^2)。因此，这里我转变思维，从逐一数字的横向比较，转变为纵向的逐位比较，来优化时间复杂度。

对于每一个数的某一位来说，若当前位为 1，那么对于当前位来说，所有数字的同位上为 0 的个数即当前数字当前位的汉明距离。因此，每一位的汉明距离为0出现的次数乘以1出现的次数，最后遍历32位即可。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        res = 0
        for i in range(32):
            c0 = 0
            c1 = 0
            # 遍历数组
            for j in range(len(nums)):
                # 统计当前位1的个数
                if (nums[j] >> i) & 1:
                    c1 += 1
                # 统计当前位0的个数
                else:
                    c0 += 1
            # 总的汉明距离加上当前位的汉明距离
            res += c0 * c1
        return res
  • 时间复杂度：O(32∗n)=O(n)

只出现一次的数字(Single Number)相关题目

136-只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2
输入: [2,2,1]
输出: 1

示例 2:

1
2
输入: [4,1,2,1,2]
输出: 4

思路

我们可以利用异或的性质：0和一个数异或后得到那个数，两个相同的数异或后则为0。

显然将所有数字异或后，得到的结果即为出现一次的值。

Python实现

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for i in range(len(nums)):
            res = res ^ nums[i]
        return res
  • 时间复杂度：O(n) 。我们只需要将 nums 中的元素遍历一遍，所以时间复杂度就是 nums 中的元素个数。
  • 空间复杂度：O(1) 。

137-只出现一次的数字ii

问题描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2
输入: [2,2,3,2]
输出: 3

示例 2:

1
2
输入: [0,1,0,1,0,1,99]
输出: 99

思路

根据题目要求，我们可以设计这样一个状态机：

a b
初始状态： 0 0
第一次碰见某个数x： 0 x 把x记录在b中
第二次碰见某个数x： x 0 把x记录在a中
第三次碰见某个数x： 0 0 把a和b都清空，可以处理其他数

我们按照上述变换规则设计a和b：

  • b=0时碰到x，就变成x；b=x时再碰到x，就变成0，这个就是异或，我们也许可以设计b=b xor x。当b再次碰到x，这时候b还是要为0，但这时候不同的是a=x，而前两种情况都是a=0。所以我们可以设计成b=(b xor x)&~a
  • 同样道理，我们可以设计出：a=(a xor x)&~b

按照这个设计，最后那个只出现一次的元素必定存储在b中。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        b = 0
        for i in range(len(nums)):
            b = (b ^ nums[i]) & ~a
            a = (a ^ nums[i]) & ~b
        return b
  • 时间复杂度：O（n）。
  • 空间复杂度：O（1）。

260-只出现一次的数字iii

问题描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

1
2
输入: [1,2,1,3,2,5]
输出: [3,5]

注意：结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

思路

由于这两个数不相等，所以异或结果不为0，也就是说二进制中至少有一位1，记为第n位。我们以第n位是否为1，来把数组分为两个子数组。

然后这个问题就相当于分别在两个数组中找一个只出现一次的元素。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 所有数异或
        x = 0
        for i in range(len(nums)):
            x = x ^ nums[i]
        
        # 由于两个出现一次的元素不相同，所以至少有一位为1，下面我找到最低那个1
        mask = 1
        while x & mask == 0:
            mask = mask << 1
        
        # 所有数根据mask=1或者0分成两组（两个特殊的数字被分为两组）
        a1 = 0
        a2 = 0
        for i in range(len(nums)):
            if nums[i] & mask == 0:
                a1 = a1 ^ nums[i]
            elif nums[i] & mask == mask:
                a2 = a2 ^ nums[i]
        return [a1,a2]

反转相关题目

190-颠倒二进制位

题目描述

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

  • 输入: 00000010100101000001111010011100
  • 输出: 00111001011110000010100101000000
  • 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

  • 输入：11111111111111111111111111111101
  • 输出：10111111111111111111111111111111
  • 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。

思路

从最低位到最高位逐位检查n的第i位是不是为1，如果是, 就把res的第31-i位设为1。

Python实现

1
2
3
4
5
6
7
8
9
class Solution:
    def reverseBits(self, n):
        res = 0
        mask = 1
        for i in range(32):
            if n & mask == mask:
                res = res | (1 << 31-i)
            mask = mask << 1
        return res

476-数字的补数

题目描述

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

注意:给定的整数保证在32位带符号整数的范围内。你可以假定二进制数不包含前导零位。

示例 1:

  • 输入: 5
  • 输出: 2
  • 解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。

示例 2:

  • 输入: 1
  • 输出: 0
  • 解释: 1的二进制表示为1（没有前导零位），其补数为0。所以你需要输出0。

思路

首先要求得二进制数的位数，然后构造一个长度等于二进制数长度的全1的数，然后异或即可得到补数。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findComplement(self, num: int) -> int:
        mask = 1
        res = 0

        while num >= mask:
            # 除首位外全1的数
            res = res | mask
            # 0b1、0b10、0b100...
            mask = mask << 1

        return num ^ res

全组合相关题目

78-子集

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

思路

数组的每个元素，可以有两个状态：

  1. 不在子数组中（用 0 表示）；
  2. 在子数组中（用 1 表示）。

那么得到的组合序列一共有2^N个, 其中00...00表示所有元素都不取，00...01表示只取第一个，依次类推。

下面是一个例子：

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        size = len(nums)  # 数组长度
        n = 1 << size     # 位掩码个数
        res = []
        for i in range(n):
            temp = []
            # 根据当前位掩码是否为1决定是否加入数组该位
            for j in range(size):
                if i >> j & 1:
                    temp.append(nums[j])
            res.append(temp)
        return res

数学相关题目

29-两数相除

题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

  • 输入: dividend = 10, divisor = 3
  • 输出: 3

示例 2:

  • 输入: dividend = 7, divisor = -3
  • 输出: -2

说明:

  • 被除数和除数均为 32 位有符号整数。
  • 除数不为 0。
  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

思路

题目中要求我们不能用乘法和除法，但是我们可以用减法，我们可以通过被除数最多可以减多少个除数还能保证是非负来得到商。

$$
dividend=quotient∗divisor+remainder
$$

不过这样在某些情况会超时（比如2**30/1），为了解决效率问题，可以减去除数的倍数，利用位运算，每次除数左移一位（2倍），次数相应加对应的倍数。然后再判断当前的和是否大于被除数，如果大于的话，再把除数回置（右移）。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 求最后结果的符号
        sign = (dividend > 0) ^ (divisor > 0)
        dividend = abs(dividend)
        divisor = abs(divisor)

        # 被除数减去除数
        quotient = 0
        # 除数加倍直到超过剩余的被除数
        count = 0
        while dividend - (divisor << count) >= 0:
            quotient += (1 << count)
            dividend -= (divisor << count)
            count += 1
        # 除数减半直到count=0
        while count > 0:
            count -= 1
            if dividend - (divisor << count) >= 0:
                quotient += (1 << count)
                dividend -= (divisor << count)

        # 负数处理
        if sign:
            quotient = -quotient 
        
        # 最大数处理
        if quotient > 2147483647:
            quotient = 2147483647
        
        # 最小数处理
        if quotient < -2147483648:
            quotient = -2147483648
        
        return quotient

201-数字范围按位与

题目描述

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1:

  • 输入: [5,7]
  • 输出: 4

示例 2:

  • 输入: [0,1]
  • 输出: 0

思路

此题其实就是寻找[m,n]范围内二进制数高位（左边）没有变化的数（由于是按位与，那么某位一旦出现0，结果该位肯定是0），后面补上0即为所求的结果。

举个例子：

  • 范围：[26,30]
  • 公共部分：11010、11011、11100、11101、11110

Python实现

我们可以建立一个31位都为1的mask，然后每次左移一位，比较m & mask和n & mask是否相同。

1
2
3
4
5
6
class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        mask = (1 << 31) - 1
        while (m & mask) != (n & mask):
            mask = mask << 1
        return m & mask

371-两整数之和

问题描述

不使用运算符 + 和 - ​​​​​​​，计算两整数 ​​​​​​​a 、b ​​​​​​​之和。

示例 1:

1
2
输入: a = 1, b = 2
输出: 3

示例 2:

1
2
输入: a = -2, b = 3
输出: 1

思路

题目说不能使用运算符 + 和 -，那么我们就要使用其他方式来替代这两个运算符的功能。

我们可以把 a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)：

  • 无进位加法使用异或运算计算得出
  • 进位结果使用与运算和移位运算计算得出

循环此过程，直到进位为 0。

注意：由于Python整数不是32位，为了让负数结果能够正确表示，需要做一定处理。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        # 2^32
        MASK = 0x100000000
        # 整型最大值
        MAX_INT = 0x7FFFFFFF
        MIN_INT = 0x80000000

        while b != 0:
            # 不考虑进位加法
            sums = a ^ b
            # 进位
            carry = (a & b) << 1

            # 取余范围限制在 [0, 2^32-1] 范围内
            a = sums % MASK
            b = carry % MASK
        
        # 处理Python整数不是32位问题（负数的正确表示）
        if a <= MAX_INT:
            return a
        else:
            return ~((a % MIN_INT) ^ MAX_INT)

其他类型题目

693-交替位二进制数

问题描述

给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。

示例 1:

  • 输入: 5
  • 输出: True
  • 解释: 5的二进制数是: 101

示例 2:

  • 输入: 7
  • 输出: False
  • 解释: 7的二进制数是: 111

思路

我们可以用把这个二进制和右移1位后的数进行异或，根据得到的数是否为全1来判断是否是交替二进制数。

Python实现

1
2
3
4
5
6
7
8
class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        a = n ^ (n >> 1)
        # 判断a是否为全1
        if a & (a + 1) == 0:
            return True
        else:
            return False
推荐文章

----------- 本文结束啦感谢您阅读 -----------

赞赏一杯咖啡
disqus valine