算法长征（14）位运算

发表于 更新于 分类于 ， 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 4 分钟

位运算

  • https://www.runoob.com/python/python-operators.html

a 为 60，b 为 13

1
2
a = 0011 1100
b = 0000 1101

image-20220603165450958

一、位运算技巧

  • n &= n - 1: 把 n 的二进制位中的最低位的 1 变为 0.
1
2
3
4
5
6
def countOnes(x: int) -> int:
		ones = 0
  	while x > 0:
				x &= (x - 1)
        ones += 1
    return ones

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def myPow(self, x: float, n: int) -> float:
        # 快速幂
        if x== 0:
            return 0
        res = 1
        if n < 0:
            x, n = 1 / x, -n
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1 # n // 2
        return res

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1
            n &= n - 1
        return res
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            if n&1 == 1:
                res += 1
            n >>= 1
        return res

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

1
2
3
4
5
6
7
class Solution:
    def add(self, a: int, b: int) -> int:
        # 无进位和: 异或运算^ 规律相同
        # 进位: 与运算& 规律相同（并需左移一位）
        if b == 0:
            return a
        return add(a ^ b, (a & b) << 1)

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？

全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 0，不同结果为 1。那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。

那么这一方法如何扩展到找出两个出现一次的数字呢？

如果我们可以把所有数字分成两组，使得：

  • 两个只出现一次的数字在不同的组中；

  • 相同的数字会被分到相同的组中

那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。

那么如何实现这样的分组呢？

  • 在异或结果中找到任意为 11 的位。
算法：
  • 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
  • 在异或结果中找到任意为 1 的位。
  • 根据这一位对所有的数字进行分组。
  • 在每个组内进行异或操作，得到两个数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        ret = functools.reduce(lambda x, y: x ^ y, nums)
        div = 1
        while div & ret == 0:
            div <<= 1
        a, b = 0, 0
        for n in nums:
            if n & div:
                a ^= n
            else:
                b ^= n
        return [a, b]

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

  • 有限状态机、遍历统计
算法：
  • 首先，将所有数字都看成 32位 的二进制数；
  • 接着，将数组中的所有数字相加。那么，对于"某一位"来说，数值一定是 3N或3N+1 ；
  • 为什么？所有出现3次的数字对该位置的贡献，和一定是0或3，出现一次的数字对该位置的贡献，一定是0或1
  • 所以，对该位置的和，用3取余，结果就是出现一次的数字在该位置的值。

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counts = [0] * 32
        for num in nums:
            for j in range(32):
                counts[j] += num & 1
                num >>= 1
        res, m = 0, 3
        for i in range(32):
            res <<= 1
            res |= counts[31 - i] % m
        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def countBits(self, n: int) -> List[int]:
        # o(nlogn)
        def countbits(x: int) -> int:
            ones = 0
            while x > 0:
                x &= (x - 1)
                ones += 1
            return ones
        return [countbits(i) for i in range(n + 1)]
    def countBits(self, n: int) -> List[int]:
        bits, high = [0], 0
        for i in range(1, n + 1):
            if i&(i - 1) == 0:
                high = i
            bits.append(bits[i - high] + 1)
        return bits