位运算

基础

位运算基础可以见python基础知识

计算位运算计算时间为O(1)

移位运算

  • 左移:

  • 逻辑右移: 就是不考虑符号位，右移一位，左边补零即可

  • 算术右移: 考虑符号位，右移一位，若符号位为1，就在左边补1；否则，就补0

算术右移也可以进行有符号位的除法，右移n位就等于除2的n次方

🍆n>>1是向下取整，n/2是整数除法，是向0取整

1
2
3
4
5
6
7
[(i // 2, i >> 1) for i in range(10)]
# 输出
[(0, 0), (0, 0),
 (1, 1), (1, 1),
 (2, 2), (2, 2),
 (3, 3), (3, 3),
 (4, 4), (4, 4)]

位运算小技巧

  1. 用异或实现配偶

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    0, 1
    2, 3
    4, 5
    6, 7

    0 ^ 1 = 1, 1 ^ 1 = 0
    2 ^ 1 = 3, 3 ^ 1 = 2
    ...
    4 ^ 1 = 5, 5 ^ 1 = 4
    ...
    1
    2
    3
    4
    5
    6
    7
    8
    [i ^ 1 for i in range(10)]
    Out[3]: [1, 0, 3, 2, 5, 4, 7, 6, 9, 8]
    [i ^ 2 for i in range(10)]
    Out[4]: [2, 3, 0, 1, 6, 7, 4, 5, 10, 11]
    [i ^ 3 for i in range(10)]
    Out[5]: [3, 2, 1, 0, 7, 6, 5, 4, 11, 10]
    [i ^ 4 for i in range(10)]
    Out[6]: [4, 5, 6, 7, 0, 1, 2, 3, 12, 13]

  1. lowbit运算: 求1最低的位数

    1
    2
    3
    4
    5
    lowbit = lambda n: (-n) & n
    或
    lowbit = lambda n: (~n+1 ) & n

    lowbit(11110010000) = 10000

  1. 判断奇偶

    只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数

  2. 取一个数中指定位

    取X的低4位，用 X & 0000 1111 = 00001110 即可得到

  3. 对一个数的某些位置1

    找到一个数，对应X要置1的位，该数的对应位为1，其余位为零。此数与X相或可使X中的某些位置1

  4. 使特定位翻转

    使特定位翻转，该数对应X要翻转的对应位为1，其余位为零，此数与X对应位异或即可

    例：X=10101110，使X低4位翻转，用X ^0000 1111 = 1010 0001即可得到

  5. 异或的几条性质：异或其实就是不进位加法

    1、交换律 a ^ b = c ===> a ^ c = b , b ^ c = a

    2、结合律 即 (a ^ b) ^ c == a ^ (b ^ c)

    3、对于任何数x，都有x ^ x = 0，x ^ 0 = x

    4、自反性: a ^ b ^ b = a ^ 0 = a

  6. 1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间

    将所有的数全部异或，得到的结果与1 ^ 2 ^ 3 ^ … ^ 1000的结果进行异或，得到的结果就是重复数

  7. 枚举一个无重复字符串所有子集的技巧

    用二进制数组表示单词中那些字母出现（1表示），那些没出现（0表示），找出该单词的所有子集。
    ace 对应二进制 int origin = 21 (二进制10101)，包含的子集(n代表子集,初始 n = origin)有：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    ace 10101
    ce 10100
    ae 10001
    ac 00101
    e 10000
    c 00100
    a 00001
    遍历核心代码：n = (n - 1) & origin;// n-1 AND puzzleBit，生成一个puzzleBit的新的子集合
    可以自己手动推算一下，是对的，n刚好遍历完所有情况

    找map中 存在的 字符串str = ace（必含有首字母a）子集的个数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int first = 1 << (str[0] - 'a');
    while (n > 0) { // 遍历origin 的所有字母组合，当n=0时终止遍历
               // 按位都是1才为1，否则为0，即n这个组合包含origin 的首字母
               // 而且n这个组合在map中有值，即有单词长n这样，值累加给res[i]
               if ((n & first) != 0 && map[n] > 0) {
                   res[i] += map[n];
               }
               // n-1 AND puzzleBit，生成一个puzzleBit的新的子集合
               n = (n - 1) & puzzleBit;
           }

  1. 常用位运算公式

    a >> b & 1 代表检查 a 的第 b 位是否为 1，有两种可能性 0 或者 1

    a += 1 << b 代表将 a 的第 b 位设置为 1 (当第 b 位为 0 的时候适用)

状态压缩

定义

二进制状态压缩，是指将一个长度为$m$的bool数组用一个$m$位二进制整数表示并存储的方法

利用下列位运算操作可以实现原bool数组中对应下标元素的存取

操作 运算
取出整数$n$在二进制表示下的第$k$位 n >> k & 1
取出整数$n$在二进制表示下的第$0 \sim k-1$位(后$k$位) n & ((1 << k) - 1)
把整数$n$在二进制表示下的第$k$位取反 n ^ (1 << k)
对整数$n$在二进制表示下的第$k$位赋值$1$ n $\vert$ (1 << k)
对整数$n$在二进制表示下的第$k$位赋值$0$ n & (~(1 << k))

这种方法运算简便，并且节省了程序运行的时间和空间

  • 当$m$不太大时，可以直接使用一个整数类型存储
  • 当$m$较大时，可以使用若干个整数类型(int数组)，也可以直接利用C++ STL为我们提供的bitset实现

案例

a^b

题目

描述

求a的b次方对p取模的值

难度

简单

输入格式

三个整数a,b,p，在同一行用空格隔开

输出格式

输出一个整数，表示$(a^b) \% p$的结果

数据范围

输入样例

1
2
3 2 7
123456789 0 1

输出样例

1
2
2
0

思路

快速幂

1
2
3
4
5
6
7
8
9
10
11
3 ^ 10000000

# 先计算出
3 ^ 1 = 3
3 ^ 2 = 9
3 ^ 4 = 81
3 ^ 8 = 
3 ^ 16 = 
3 ^ 32 = 
...
3 ^ (2^19) = xxx

🥕核心: 再看下10000000的二进制表示，把对应为1的位乘起来就可以

10000000的二进制表示为0b100110001001011010000000，因此只要对应位置的值乘起来就是3 ^ 10000000

🥕根据数学常识，每一个正整数可以唯一表示为若干指数不重复的2的次幕的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def ck_sum_of_power(in_n: int):
    """
    检验整数可以由若干个不重复的2的次幂的和
    @param in_n:
    @return:
    """
    nb = in_n
    res = 0
    v = 1
    while nb:
        if nb & 1:
            res += v
        v *= 2
        nb >>= 1
    return res


if __name__ == '__main__':
    print(all([ck_sum_of_power(in_n=i) == i for i in range(100)]))

也就是说，如果b在二进制表示下有$k$位，其中第$i(0<i<k)$位的数字是$c_i$，则

于是

因为$k= \lceil log2(b+1) \rceil $，所以上式乘积项的数量不多于$\lceil log2(b+1) \rceil$个

又因为$a^{2^i} = {a^{(2^{i-1})}}^2$，所以我们很容易通过$k$次递推求出每个乘积项，当$c_i=1$时，把该乘积项累积到答案中

b&1运算可以取出b在二进制表示下的最低位，而b>>1运算可以舍去最低位，在递推的过程中将二者结合，就可以遍历b在二进制表示下的所有数位$c_i$，整个算法的时间复杂度为O($log2(b)$)

求解

1
2
3
4
5
6
7
8
9
10
11
12
def solution(a: int, b: int, p: int) -> int:
    res = 1 % p
    while b:
        # 如果b的个位是1
        if b & 1:
            res = res *  a % p
        # 准备十位
        a = a * a % p
        # 去掉各位
        b >>= 1

    return res

a*b%p

题目

描述

求a乘b次方对p取模的值

难度

简单

输入格式

三个整数a,b,p，在同一行用空格隔开

输出格式

输出一个整数，表示$(a*b) \% p$的结果

数据范围

输入样例

1
2
3 4 5
111 999 1000000

输出样例

1
2
2
110889

思路

1
2
3
4
5
6
7
8
a * b

a * 1 = a
a * 2 = 2a
a * 4 = 4a
a * 8 = 8a
...
a * (2^k) = (2^k) * a

求解

1
2
3
4
5
6
7
8
9
def solution(a: int, b: int, p: int) -> int:
    res = 0
    while b:
        if b & 1:
            res = (res + a) % p
        a = a * 2 % p
        b >>= 1

    return res

最短Hamilton路径

哈密顿路径

哈密顿路径也称作哈密顿链，指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完全(NP-complete）问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP完全的

旅行商问题

旅行商问题 (Traveling Salesman Problem，TSP)，又叫货郎担问题，它是图论中一个经典的组合优化问题。

经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市一次并且仅一次之后后，回到出发城市。问他应如何选择在城市之间的行程路线，以使他走过的总路程最短。

从图论的角度来看，该问题其实就是在一个赋权的无向图中，去找一个哈密尔顿回路，并且使得该回路的总权值最小。

容易看出，旅行商问题的可行解是N个顶点的全排列(把[1,2,3,4，…,N]打乱顺序随机排列)，其可行解的个数有N!个，也就是路线有N!个。

如果按照穷举法将N!个可行解一一找出来，然后从中找出行程最短的路线。随着顶点数N的增加，会产生组合爆炸。从计算复杂性的角度来看，它是NP-完全问题

拓展

P问题，NP问题，NPC问题，NP-Hard问题

题目

描述

给定一张 $n$ 个点的带权无向图，点从 $0∼n−1$ 标号，求起点 $0$ 到终点 $n−1$ 的最短 Hamilton 路径。

Hamilton 路径的定义是从 $0$ 到 $n−1$ 不重不漏地经过每个点恰好一次。

难度

中等

输入格式

第一行输入整数 $n$

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离（记为 $a[i,j]$]）

对于任意的 $x,y,z$，数据保证 $a[x,x]=0, a[x,y]=a[y,x]$ 并且 $a[x,y]+a[y,z] \geq a[x,z]$

输出格式

输出一个整数，表示最短 Hamilton 路径的长度

数据范围

输入样例

1
2
3
4
5
6
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例

1
18

思路

考虑两个点

  • 哪些点被用过
  • 目前停在哪个点上

第一维有$n$个点，取值为0或1，表示用或不用

第二维有$n$个点，所以状态矩阵大小为

使用暴力方法，状态数为$2^{20}$

接下来考虑每个状态是如何计算的

$state_k$是$state$去掉$j$之后的集合，$state_k$要包含$k$

关键点

这里可以用二进制的整数表示$state$

比如包含$0,1,4$，则$state=10011$

求解

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
36
37
38
39
40
def solution(n, f, weight):
    # 一开始停在0,0被选中故状态位为00..0001, 此时的距离为0
    f[1][0] = 0

    # 枚举
    for i in range(1 << n):
        # 最后停留的位置
        for j in range(n):
            # i的二进制下第j位是不是1
            if i >> j & 1:
                for k in range(n):
                    # 此时 i^(1 << j) == n & (~(1 << k))表示i的第j位取反
                    # 并且第k位为1(表示有路径到达j)
                    if i ^ (1 << j) >> k & 1:
                        # 更新最短路径
                        f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + weight[k][j])


if __name__ == '__main__':
    N, M = 20, 1 << 20
    # f[i][j]表示状态是i的情况下，停在点j的最小路径是多少
    f, weight = [], []
    for i in range(M):
        f.append([1e10] * N)
    for i in range(N):
        weight.append([0] * N)

    # 输入n和权重
    # n: int = int(input())
    # weight = input()
    n = 5
    s = """0 2 4 5 1
           2 0 6 5 3
           4 6 0 8 3
           5 5 8 0 5
           1 3 3 5 0"""
    weight = [[int(j) for j in i.strip().split(' ')] for i in s.split('\n')]

    solution(n=n, f=f, weight=weight)
    print(f[(1 << n) - 1][n - 1])

强调一下(1<<n)-1的意思：1<<n是将1左移n位也就是10000…(n个0)，减去1以后就会是1111…(n个1)，理解一下，前一个数是n+1位，后一个数是n位，所以说此时(1<<n)-1也就是所有位都是1