位运算

1.知识

bit 是度量信息的单位，包含0和1两种状态。计算机的各种运算最后无不归结为一个个bit的变化。

符号	含义
&	与
\|	或
~	按位取反
^	异或
>>	右移（算术右移，高位补符号）
<<	左移（算术左移，低位补0）

按位取反举例
补码的补码就是原码，在计算机中存储全是补码，
十进制数1的二进制补码为：00000001
取反后补码为：11111110
求这个补码的原码：10000010（屏幕上显示都是原码-2）所以1取反后等于-2
在补码下，每个数值都有唯一的表示方式，并且任意两个数值做加减法运算，都等价于在32位补码下做最高位不进位的二进制加减法运算。发生算术溢出时，相当于自动对2^32^取模。所以要注意两个大整数相加有可能是负数。

例题1

求a的b次方对p取模的值，其中1<=a,b,p<=10^9^. (POJ1995 raising modulo numbers)

每个正整数可以唯一表示为若干指数不重复的2的次幂的和。也就是说如果b在二进制表示下有k位，其中第i位的数字是c~i~，那么：
b=c~k-1~2^k-1^+c~k-2~2^k-2^+ ... +c~0~2^0^

则： $ a^b = a^{c_{k-1}*2^{k-1}}*a^{c_{k-2}*2^{k-2}}*...*a^{c_0*2^0}$

又因为 $ k=\lceil \log (b+1) \rceil $

所以上式乘积项的数量不多于k个，算法为log级

$ a^{2^i}=(a^{2^{i-1}})^2 $

所以我们可以通过k次递推求出每个乘积项，当c~i~=1时，把该项累积到答案中。b&1运算可以取出b在二进制表示的最低位，而b>>1运算可以舍去最低位，在递推的过程中将二者结合，就可以遍历b在二进制表示下的所有数位c~i~.

int pow(int a,int b,int p)
{
    int ans = 1 % p;
    a %= p;
    for(;b;b>>=1)
    {
        if(b&1) ans=(long long) ans * a % p;
        a = (long long) a * a % p;
    }
    return ans;
}

例题2

求a乘b对p取模的值，1<=a,b,p<=10^18^

类似于快速幂：

$ a*b=c_{k-1}*a*2^{k-1}+c_{k-2}*a*2^{k-2}+...+c_0*a*2^0 $

因为 $ a*2^i=(a*2^{i-1})*2 $ ，如果已经求出来 $ a*2^{i-1}\% p$ ，则可以利用递推求出 $ a*2^{i}\% p$ ，运算过程中每一步的结果都不超过2*10^18^，可以利用k次递推求出每个乘积项。当c~i~=1时，把该乘积项累加到答案中即可。

typedef long long ll;
ll mul(ll a,ll b,ll p)
{
    ll ans=0;
    for(;b;b>>=1)
    {
        if(b&1) ans=(ans+a)%p;
        a=a*2%p;
    }
    return ans;
}

当然，也可以利用 $ a*b\%p=a*b-\lfloor a*b/p \rfloor *p $
首先在a,b<p时，c=a*b/p向下取整以后一定小于p。我们可以用浮点数执行a*b/p的运算，而不用关心小数点后的部分。long double 在十进制下的有效数字有18~19位，足够胜任。当浮点数的精度不足时，它会像科学计数法一样舍弃低位，正好符合我们的要求。

另外，a*b和c*p可能很大，但是二者的差一定在0~p-1之间，我们只关心它们较低的若干位即可。用long long保存结果，整数运算溢出相当于舍弃高位，也正好符合要求。

typedef long long ll;
ll mul(ll a,ll b,ll p)
{
    a %= p; b %= p;
    long long c=(long double) a*b/p;
    long long ans= a*b-c*p;
    if(ans<0) ans+=p;
    else if(ans>=p) ans-=p;
    return ans;
}

2.成对变换

我们通过计算可以发现，对于非负整数n：

当n为偶数时，n ^ 1 等于 n+1

当n为奇数时，n ^ 1 等于 n-1

因此0和1，2和3，4和5，这些数对都是关于异或“成对变换”，这个性质经常用于图论，可以通过异或运算获得当前边的反向边编号。但为了安全起见，最好边的编号最好从2开始。

3.lowbit运算

lowbit(n) 取出非负整数n在二进制表示下最低位的1以及后边的0构成的数值。

设n>0，n的第k位是1，第0~k-1位都是0。为了实现lowbit，先把n取反，此时第k位变成0，第0~k-1都是1.再令n=~n+1，此时因为进位，第k位变为1，第0~k-1变成0.

由此可知，n和~n+1在第k+1到最高位的每一位都刚好相反，第k位都是1，第0到第k-1位都是0，这样一来，n & ~n+1 之后，就剩下第k位的1，其余位都是0.而在补码表示下，~n = -1-n，因此：
lowbit(n) = n & (~n+1) = n & -n

lowbit 是树状数组的核心操作。

lowbit 配合hash可以找到整数二进制表示下所有是1的位，所花费的时间与1的个数同级。

const int maxn_n = 1 << 20;
int H[maxn_n];
int n;
int main()
{
    for(int i=0;i<=20;i++) H[1<<i]=i; //预处理出某个数字在第几位
    while(cin >> n)
    {
        while(n>0)
        {
            cout<<H[n & -n] << ' ';
            n-=n&-n;
        }
    }
}

4.二进制状态压缩

二进制状态压缩，是指将一个长度为m的bool数组用一个m位二进制整数表示并存储的方法。利用下列位运算操作可以实现原bool数组中对应下标元素的存取。

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

这种方法运算简便，并且节省了程序运行的时间和空间。当m不大时，可以直接使用一个整数类型存储。当m较大时，可以使用若干个整数类型（int数组），也可以直接利用bitset实现。

例题3

给定一张n(n<=20)个点的带权无向图，点从0~n-1标号，求起点0到终点n-1的最短hamilton路径。hamilton路径的定义是从0到n-1不重不漏地经过每个点恰好一次。（洛谷1171，扩展题目：POJ2288 Islands and Bridges）

思路点拨：
很容易想到一种朴素的做法，就是枚举n个点的全排列，计算路径长度，取最小值，时间复杂度为O(nn!)，可以使用状态压缩dp将其优化到O(n^2^2^n^)

在任意时刻，要表示出哪些点被走过，哪些点没有被走过，可以用一个n位二进制数，若其第i位(0<=i<n)为1，则表示第i个点已经被经过，反之未被经过。在任意时刻还需要知道当前所处的位置，因此使用Fi,j表示点被经过的状态对应的二进制数为i，且目前处于点j时的最短路径。

初始值F[1,0]，即只经过了点0（i只有第0位是1），目前处于起点0，最短路径长度为0。方便起见，将F的其他值设为极大值，目标状态为F[(1<<n)-1,n-1]，即经过所有点（i的所有位都是1），处于终点n-1的最短路。

在任意时刻，有公式F[i,j]=min{F[i ^ (1<<j),k]+weight(k,j)},0<=k<n并且((i>>j)&1)=1，即当前时刻“被经过的点的状态”对应的二进制数为i，处于点j。因为j只能恰被经过1次，所以一定是刚刚经过的，故在上一时刻“被经过的点的状态”对应的二进制数的第j位应该赋值为0，也就是i^(1<<j)。另外，上一时刻所处的位置可能是i^(1<<j)中任意一个是1的位置k，从k走到j需要weight(k,j)，可以考虑取所有这样的k取最小值。

int f[1<<20][20];
int main()
{
    memset(f,0x3f,sizeof f);
    f[1][0]=0;
    for(int i=1;i<(1<<n);i+=2) 
    {
        for(int j=0;j<n;j++)
        {
            if(!((i >> j) & 1)) continue; //当前i状态下，根本没有走过j
            for(int k=0;k<n;k++)
            {
                if(j==k) continue;
                if(!(i>>k & 1)) continue; //上一次状态，根本没有走过k，就更不可能从k转移到j
                f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]);
            }
        }
    }
    cout << f[(1<<n)-1][n-1]; // 所有点走完，最后停在n-1点上
}