常用操作

最右一位为第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))

 

二进制状态压缩例题： 最短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<

 

lowbit

表示非负整数n在二进制下最低位1以及它后面的0构成的数值

比如

lowbit(n) = 100

lowbit(n) = n & (-n)

 

快速求二进制中1的个数

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

x & (x - 1) 可以把二进制中最后一位1去掉

比如10100变成10000

这里减去lowbit(x)也可以