位运算算法合集

  发表  更新  Algorithm  25 分钟读完 (大约3718个字)  0次访问

基本操作

左移 <<

左移运算符实现将数字的所有二进制位向左移动一位，最高位移出数据，最低位补 0。一般也称为逻辑左移。

如果 n 为32位二进制数据，则左移相当于：(n<<i)=(n∗2i)mod  232=(nmod  231)∗2i(n << i) = (n * 2^i) \mod 2^{32} = (n \mod 2^{31}) * 2^i

右移 >>

右移运算符实现将数字的所有二进制位向右移动一位，最低位移出数据，最高位补 0 或 符号位。根据最高位的不同，可以分为两种，一种为逻辑右移，最高位全部补 0，一种为算术右移，最高位补符号位，也即正数补 0，负数补 1。

一般情况下，编程语言中对右移运算符的实现为：若操作数为无符号数，则使用逻辑右移；若为有符号数，则使用算术右移。

如果 n 为32位二进制数据，则右移相当于：(n>>i)=(n−(n%2i))/2i(n >> i) = (n - (n \% 2^i)) / 2^i

与 &

x y z = x & y
0 0 0
0 1 0
1 0 0
1 1 1
  • 如果固定 x = 0，则输出 z = 0。使用此性质可以实现对特定的位进行置 0。
  • 如果固定 x = 1，则输出 z = y。使用此性质可以实现对特定的位进行取数。
  • 如果 n 为32位 bit 数据，则通过 (n >> i) & 1 可以得到第 i 位的数字。（下标从 0 开始）

或 |

| x | y | z = x | y |
| :—: | :—: | :---------: |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

  • 如果固定 x = 0，则输出 z = y。使用此性质可以实现对特定的位进行取数。
  • 如果固定 x = 1，则输出 z = 1。使用此性质可以实现对特定的位进行置 1。

非 ~

x ~ x
0 1
1 0
  • 非门可用于求操作数的补码，根据补码定义，数 n 的补码为：(~ n) + 1

异或 ^

x y z = x ^ y
0 0 0
0 1 1
1 0 1
1 1 0
  • 如果固定 x = 0，则输出 z = y。使用此性质可以实现对特定的位进行取数。
  • 如果固定 x = 1，则输出 z = ~ y。等同于非运算符。
  • x ^ x = 0
  • x ^ y = z 可以得到：x ^ z = y， y ^ z = x

同或 ~^

x y z = ~ (x ^ y)
0 0 1
0 1 0
1 0 0
1 1 1
  • 用得较少，性质与异或相似。

基本操作

在这里，我们假设所有的数字都是 32 位无符号数，用 x, y, z, n 表示，在需要有符号数处会进行说明。

使用 i, j, k 来表示数据的特定位，其中 0 <= i, j, k < 32。

同时，我们使用 a, b, c 来表示单个 bit 数据，也就是 0 / 1。

生成 2 的 i 次幂

  • 左移：1 << i

取第 i 位数字

  • 右移 + 与门：(n >> i) & 1
  • 与门 + 右移：(n & (1 << i)) >> i
  • 右移 + 取余 + 或门：((n >> i) % 2) | 0

对第 i 位置 0

  • 左移 + 非门 + 与门：n & (~ (1 << i))

对第 i 位置 1

  • 左移 + 或门：n | (1 << i)

清除最后的 1

  • 减法 + 与门：n & (n - 1)

#136 - 只出现一次的数字

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

对于这道题，最简单的办法就是使用一个哈希表，统计所有元素出现的次数，最后返回只出现一次的那个元素。但是这样的方法需要 O(n)O(n) 的空间，并不是一个很优秀的算法。

那么，如果使用位运算来做这个题，该怎么办呢？

首先，我们想要保留的是只出现一次的数字，也就是说出现两次的数字都需要消除掉，而这样的要求可以通过异或来实现：

  • 由于 x ^ x = 0，因此可以保证任何出现两次的数字都会相互抵消，只剩下 0
  • 由于 x ^ 0 = x，因此可以保证只出现一次的数字可以保留在结果之中

有了这样的思路，程序的编写就很简单了。首先，我们初始化一个变量 ans = 0，接着遍历整个数组，将 ans 与每个数字都进行异或，最终遍历完成之后 ans 中的数字便是本题想要得到的元素。

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for x in nums:
        	ans ^= x
        return ans

其他变体

#137 - 只出现一次的数字 II

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

与上面那道题比起来，本题只修改了一处，即是重复的数字每个出现三次。由于异或运算对于出现奇数次的数字都会保留下来，因此无法再像上面那道题一样对所有元素进行一遍异或求解。

但是，考虑到空间复杂度，我们仍然希望能够使用 O(1)O(1) 的空间，因此还是使用异或运算进行求解。

如果，对于一个元素，我们能够区分出它是否是第三次出现，从而在其第三次出现时，我们不将其加入到异或结果中，那么本题就和上面一道题是一致的。也就是说，我们的异或运算中，只包含出现一次的数字，和出现三次数字的前两次，因此最终的异或结果就是只出现一次的数字。

那么，现在的问题就是，如何在异或中区分出现第一次和第三次出现的数字。或者说，如何使第三次出现的元素不会加入到异或结果中。

假设我们的异或结果为 ans，其中数字 x 出现了 3 次。在与 x 完成两次异或后，此时 ans = 0，如果我们可以知道 x 是出现过两次的数字，那么在第三次时，可以通过 ans = ~x & (ans ^ x) = ~x & x = 0，使得第三个 x 对异或结果不产生任何影响。

那么怎么去判断 x 是出现过两次的数字呢？在这里我们使用另外一个变量 t，在每个 x 出现时，我们令：

  • ans = ~t & (ans ^ x)
  • t = ~ans & (t ^ x)

那么，我们可以来看一下运算的结果：

  • 初始时：ans = 0, t = 0
  • 第一次出现 x： ans = x, t = 0 ，ans 保留了出现一次的 x
  • 第二次出现 x： ans = 0, t = x ，ans 中重复出现的数字抵消，t 中保存了重复出现的数字
  • 第三次出现 x： ans = 0, t = 0 ，回到初始值。

因此，在这样的算法下，ans 中只会保存出现一次的数字，而当数字重复出现时，均会被抵消。

具体的算法如下，在算法中，为了更有意义地命名，将 ans 写为 seen_once，将 t 写为 seen_twice：

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        seen_once = seen_twice = 0
        for x in nums:
            seen_once = ~seen_twice & (seen_once ^ x)
            seen_twice = ~seen_once & (seen_twice ^ x)
        return seen_once

扩展：出现 n 次时如何求解

让我们顺势思考下面的问题：

如果有一个数字只出现 1 次，其余的数字均出现 n 次，该如何求解？

问题分析

我们可以对 n 做一个归纳：（显然 n>1n > 1 ）

  1. 当 n = 2 或 n = 3 时，上面的算法已经给出答案
  2. 当 n 为偶数时，均可使用 n = 2 地算法来解决，因为异或运算对于偶数次的运算结果是一致的
  3. 当 n 为奇数的时候呢？看起来没有一个简单的办法。

我们先来回顾一下 n = 3 时，列个表格看一下三次重复出现的数字产生了哪些变化：

seen_once seen_twice
初始值 0 0
x x 0
x 0 x
x 0 0

那么，如果 n = 5 呢，我们应该想要的也是一个类似于上面的表格：

a b c d
初始值 0 0 0 0
x x 0 0 0
x 0 x 0 0
x 0 0 x 0
x 0 0 0 x
x 0 0 0 0

从而，我们可以写出下面的迭代算法：

  • a = ~b & ~c & ~d & (a ^ x)
  • b = ~a & ~c & ~d & (b ^ x)
  • c = ~a & ~b & ~d & (c ^ x)
  • d = ~a & ~b & ~c & (d ^ x)

为什么可以这样写呢？首先，从算法上来看，每个变量都是其他所有变量的 & 并且再 & 上它与 x 的异或。

那么，什么时候当前变量会进行改变呢？很明显，就是当其他的变量都是 0，自身也是 0 的时候，这个变量会变成 x；而当其他的变量都是 0，自身是 x 的时候，这个变量会变成 0。

  1. 首先来看第一轮，由于初始值全是 0，因此 a 在第一步变为 x，而由于 a = x，因此第一轮中其他变量均不会发生变化，最后的结果为 a = x, b = 0, c = 0, d = 0
  2. 接着是第二轮，当 a 再次进行迭代时，由于其他变量全为 0，而 a = x，因此 a 会变成 0；此时轮到 b，显然此时所有变量都为 0，因此在 b 运算结束后，b 会变成 x；同时剩余的 c 和 d 均不满足变化的条件，因此仍然为 0。最后的结果为 a = 0, b = x, c = 0, d = 0
  3. 第三轮的变化也是类似的，b 从 x 变为 0，然后给了 c 一个机会从 0 变为 x，最后的结果为 a = 0, b = 0, c = x, d = 0
  4. 第四轮同样，最后的结果为 a = 0, b = 0, c = 0, d = x
  5. 到了第五轮，最终 d 由 x 变为了 0，运算结束，最后的结果为 a = 0, b = 0, c = 0, d = 0，再次回到初始值，可以进行下一次运算。

从算法的过程中可以看出，这样的运算本质上是数字 x 在相邻变量中的传递过程，最终将其清零回归初始状态。而这个算法事实上不仅仅适用于 n 为奇数，n 为偶数也同样适用，只不过偶数的情况下有更适合的算法。

算法归纳

最后，我们可以归纳出这样的算法：

对于问题：如果有一个数字只出现 1 次，其余的数字均出现 n 次，该如何求解？

  1. 首先，初始化 n - 1 个变量，均为 0，依次命名为 x1,...xn−1x_1, ... x_{n-1}
  2. 对于每个在数组中出现的数字 t：
    1. x1= x2&...&xn−1&(x1⊕t)x_1 = ~x_2 \& ... \& x_{n-1} \& (x_1 \oplus t)
    2. ......
    3. xn−1= x1&...&xn−2&(xn−1⊕t)x_{n-1} = ~x_1 \& ... \& x_{n-2} \& (x_{n-1} \oplus t)
  3. 返回 x1x_1

再次扩展

最后，如果将问题再次扩展：如果有一个数字只出现 m 次，其余的数字均出现 n 次，该如何求解？ 其中 m < n

其实观察上面的表格就可以看出，如果是要求出现 m 次的数字，只需要最后返回 xmx_m 就可以实现。

程序语言编写算法

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    # 有一个数字只出现 m 次，其余的数字均出现 n 次
    def singleNumber(self, nums，m, n):
        seen = [0] * (n - 1)
        for x in nums:  # 对于每个数字
            for i in range(len(seen)):  # 对于每个变量
                seen[i] ^= t            # 先计算异或的值
                for j in range(len(seen)):
                    if i != j:          # 对于所有其他变量
                        seen[i] &= ~seen[j]	    # 进行与运算
        return seen[m - 1]				# 返回第 m 个变量

#260 - 只出现一次的数字 III

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

这个问题稍微简单一点，首先，如果我们对所有元素进行依次异或遍历，假设只出现一次的元素为 x 和 y，那么遍历的结果为 bitmask = x ^ y，由于 x != y，那么 bitmask != 0。

如果我们按位查看 bitmask，那么一定有一位不为 0，并且在这一位上，x 和 y 一定一个为 1，一个为 0。

因此我们可以找到这一位，在这里有个技巧是 diff = bitmask & (-bitmask)，可以直接得到 bitmask 中最后一个 1 的掩码。

接着再次进行遍历，在这次遍历中，如果元素与 diff 相与为 1，说明该元素在对应位置上为 1，便将其进入到异或中，否则就略过。这样可以保证这一次的异或结果中只包含 x 和 y 其中的一个，最后返回 [x, bitmask^x] 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        bitmask = 0
        for num in nums:
            bitmask ^= num
        
        # rightmost 1-bit diff between x and y
        diff = bitmask & (-bitmask)
        
        x = 0
        for num in nums:
            # bitmask which will contain only x
            if num & diff:
                x ^= num
        
        return [x, bitmask^x]

#191 - 位1的个数

本题可以利用之前提到的，n &= n - 1 将数字最后一位 1 清除。

反复进行此操作，直至 n == 0，记录操作的次数，即为所求答案。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        while n:
            n &= n - 1
            ans += 1
        return ans

#231 - 2的幂

如果一个数字是 2 的幂，那么在二进制表示形式上，它一定只有一位为 1，因此如果使用 n & (n - 1)，那么结果一定为 0。为了消除数字 0 的影响，加上 n > 0 条件即可。

1
2
3
4
5
6
7
class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n > 0 and (n & (n - 1)) == 0

#342 - 4的幂

如果一个数字是 4 的幂，那么首先它一定是 2 的幂，因此先加上判定条件：num > 0 and (num & (num - 1)) == 0。通过这个条件的数字中有且只有一位 1。

同时，数字是 4 的幂可以表示为：num=4n=22nnum = 4^n = 2^{2n}，因此，从二进制表示上来看，1 所在的位一定是奇数位，比如：1 = 0000 0001， 4 = 0000 0100， 16 = 0001 0000，……

因此我们可以再使用一个掩码：0x55555555 = b'0101 0101 ... 0101，来判断数字 1 是否出现在奇数位。如果 num & 0x55555555 > 0，说明出现在奇数位，则数字为 4 的幂；否则不是。

同样，我们也可以使用另外一个掩码：0xAAAAAAAA = b'1010 1010 ... 1010，判定条件相应变为：num & 0xAAAAAAAA == 0。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num > 0 and \
            (num & (num - 1)) == 0 and \
            (num & 0x55555555) > 0

数字范围按位与

颠倒二进制位

位运算算法合集

http://blog.czccc.cc/p/cdd10903/

作者

Cheng

发布于

2020-10-30

更新于

2022-08-06

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

关注我
×