0 常用二进制操作

最右一位为第0位，从右到左依次为 0， 1， 2， 3……

取出n的第k位                              (n >> k) & 1
取出n的第0~k-1位                       n & ((1 << k) - 1)
n的第k位取反                              n ^ (1 << k) 
n的第k位赋值为1                         n | (1 << k)
n的第k位赋值为0                         n & (~(1 << k))

1 快速幂

http://139.196.53.116/ml/index.php/archives/173/

2 交换 x,y

x ^= y
y ^= x
x ^= y

3 表示子集

假设S={“A”,"B","C"}
111(7)->A B C
110(6)->A B
。。。
001(1)->C
000(0)->NULL空集

def subSet(nums):
    n = len(nums)
    res = []
    for i in range(2 ** n):
        cur = []
        for j in range(n):
            if i & (2 ** j) == 2 ** j:
                cur.append(nums[j])
        res.append(cur)
    return res

4 遗传算法中的 DNA

5 判断整数是否2的幂

    int isExp2(int n)
    {
        if (n<=0)    return 0;
        return n&(n-1)?0:1;
    }

6 快速求二进制中1的个数

int num(int x) { return !x ? 0 : 1 + num(x & (x - 1)); }

x & (x - 1) 可以把二进制中最后一位1去掉
比如10100变成10000
这里减去lowbit(x)也可以

7 lowbit

表示非负整数n在二进制下最低位1以及它后面的0构成的数值
比如 n = 10010101011000100
lowbit(n) = 100
lowbit(n) = n & (-n)

8 二进制状态压缩例题： 最短Hamliton路径

给定一张 n(n≤20) 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
核心代码

int f[1 << 20][20];
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
REP(i, 1, 1 << n)
    REP(j, 0, n) if((i >> j) & 1)
        REP(k, 0, n) if((i >> k) & 1)
            f[i][j] = min(f[i][j], f[i^(1<<j)][k] + w[k][j]);
printf("%d\n", f[(1<<n)-1][n-1]);

9，尼姆的取石子游戏

https://www.zhihu.com/question/20681463/answer/29306771

10，老鼠试毒药

https://blog.csdn.net/weixin_42912755/article/details/81512823
http://blog.sciencenet.cn/blog-677221-669159.html

11、如何确定黑盒子中的非负整数系数多项式

https://www.zhihu.com/question/27588576/answer/37227485

• dx版本、openGL、Vulkan与游戏
• vc++小贴士
• MinHook--CCKa_max 的Directx-11-example(64)
• c++ hookd3d imgui 一步步操作（艾鱼）
• mediapipe win10 编译、运行命令说明

发表新评论 取消回复

发送

仅有 1 条评论

1. 

   root本文作者

   1660 天前 回复

   算法竞赛进阶指南