Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"qiyijin","updateTime":1542510380000,"title":"位运算","dislikeCnt":0,"content":"# 位运算\n## 1.知识\n1. bit 是度量信息的单位,包含0和1两种状态。计算机的各种运算最后无不归结为一个个bit的变化。\n\n2.\n符号|含义\n--|:--:\n\u0026|与\n\\||或\n~|按位取反\n^|异或\n\u003e\u003e | 右移(算术右移,高位补符号)\n\u003c\u003c | 左移(算术左移,低位补0)\n\n3. 按位取反举例\n补码的补码就是原码,在计算机中存储全是补码,\n十进制数1的二进制补码为:00000001\n取反后补码为:11111110\n求这个补码的原码:10000010(屏幕上显示都是原码-2) 所以1取反后等于-2\n\n4. 在补码下,每个数值都有唯一的表示方式,并且任意两个数值做加减法运算,都等价于在32位补码下做**最高位不进位**的二进制加减法运算。发生算术溢出时,相当于自动对2^32^取模。所以要注意两个大整数相加有可能是负数。\n\n### 例题1\n求a的b次方对p取模的值,其中1\u003c\u003da,b,p\u003c\u003d10^9^. ([POJ1995 raising modulo numbers](http://poj.org/problem?id\u003d1995))\n\n每个正整数可以唯一表示为若干指数不重复的2的次幂的和。也就是说如果b在二进制表示下有k位,其中第i位的数字是c~i~,那么:\nb\u003dc~k-1~2^k-1^+c~k-2~2^k-2^+ ... +c~0~2^0^\n\n则:`$ a^b \u003d a^{c_{k-1}*2^{k-1}}*a^{c_{k-2}*2^{k-2}}*...*a^{c_0*2^0}$`\n\n又因为`$ k\u003d\\lceil \\log (b+1) \\rceil $`\n\n所以上式乘积项的数量不多于k个,算法为log级\n\n`$ a^{2^i}\u003d(a^{2^{i-1}})^2 $`\n\n所以我们可以通过k次递推求出每个乘积项,当c~i~\u003d1时,把该项累积到答案中。b\u00261运算可以取出b在二进制表示的最低位,而b\u003e\u003e1运算可以舍去最低位,在递推的过程中将二者结合,就可以遍历b在二进制表示下的所有数位c~i~.\n\n```c\nint pow(int a,int b,int p)\n{\n\tint ans \u003d 1 % p;\n\ta %\u003d p;\n\tfor(;b;b\u003e\u003e\u003d1)\n\t{\n\t\tif(b\u00261) ans\u003d(long long) ans * a % p;\n\t\ta \u003d (long long) a * a % p;\n\t}\n\treturn ans;\n}\n```\n### 例题2\n求a乘b对p取模的值,1\u003c\u003da,b,p\u003c\u003d10^18^\n\n类似于快速幂:\n\n`$ a*b\u003dc_{k-1}*a*2^{k-1}+c_{k-2}*a*2^{k-2}+...+c_0*a*2^0 $`\n\n因为`$ a*2^i\u003d(a*2^{i-1})*2 $`,如果已经求出来`$ a*2^{i-1}\\% p$`,则可以利用递推求出`$ a*2^{i}\\% p$`,运算过程中每一步的结果都不超过2*10^18^,可以利用k次递推求出每个乘积项。当c~i~\u003d1时,把该乘积项累加到答案中即可。\n\n```c\ntypedef long long ll;\nll mul(ll a,ll b,ll p)\n{\n\tll ans\u003d0;\n\tfor(;b;b\u003e\u003e\u003d1)\n\t{\n\t\tif(b\u00261) ans\u003d(ans+a)%p;\n\t\ta\u003da*2%p;\n\t}\n\treturn ans;\n}\n```\n\n当然,也可以利用`$ a*b\\%p\u003da*b-\\lfloor a*b/p \\rfloor *p $`\n首先在a,b\u003cp时,c\u003da*b/p向下取整以后一定小于p。我们可以用浮点数执行a\\*b/p的运算,而不用关心小数点后的部分。long double 在十进制下的有效数字有18~19位,足够胜任。当浮点数的精度不足时,它会像科学计数法一样舍弃低位,正好符合我们的要求。\n\n另外,a\\*b和c\\*p可能很大,但是二者的差一定在0~p-1之间,我们只关心它们较低的若干位即可。用long long保存结果,整数运算溢出相当于舍弃高位,也正好符合要求。\n\n\n```c\ntypedef long long ll;\nll mul(ll a,ll b,ll p)\n{\n\ta %\u003d p; b %\u003d p;\n\tlong long c\u003d(long double) a*b/p;\n\tlong long ans\u003d a*b-c*p;\n\tif(ans\u003c0) ans+\u003dp;\n\telse if(ans\u003e\u003dp) ans-\u003dp;\n\treturn ans;\n}\n```\n\n\n## 2.成对变换\n\n我们通过计算可以发现,对于非负整数n:\n\n当n为偶数时,n ^ 1 等于 n+1\n\n当n为奇数时,n ^ 1 等于 n-1\n\n因此0和1,2和3,4和5,这些数对都是关于异或“成对变换”,这个性质经常用于图论,可以通过异或运算获得当前边的反向边编号。但为了安全起见,最好边的编号最好从2开始。\n\n### 3.lowbit运算\n\nlowbit(n) 取出非负整数n在二进制表示下最低位的1以及后边的0构成的数值。\n\n设n\u003e0,n的第k位是1,第0~k-1位都是0。为了实现lowbit,先把n取反,此时第k位变成0,第0~k-1都是1.再令n\u003d\\~n+1,此时因为进位,第k位变为1,第0~k-1变成0.\n\n\n由此可知,n和\\~n+1在第k+1到最高位的每一位都刚好相反,第k位都是1,第0到第k-1位都是0,这样一来,n \u0026 \\~n+1 之后,就剩下第k位的1,其余位都是0.而在补码表示下,~n \u003d -1-n,因此:\nlowbit(n) \u003d n \u0026 (~n+1) \u003d n \u0026 -n\n\n\nlowbit 是树状数组的核心操作。\n\nlowbit 配合hash可以找到整数二进制表示下所有是1的位,所花费的时间与1的个数同级。\n\n```cpp\nconst int maxn_n \u003d 1 \u003c\u003c 20;\nint H[maxn_n];\nint n;\nint main()\n{\n\tfor(int i\u003d0;i\u003c\u003d20;i++) H[1\u003c\u003ci]\u003di; //预处理出某个数字在第几位\n\twhile(cin \u003e\u003e n)\n\t{\n\t\twhile(n\u003e0)\n\t\t{\n\t\t\tcout\u003c\u003cH[n \u0026 -n] \u003c\u003c \u0027 \u0027;\n\t\t\tn-\u003dn\u0026-n;\n\t\t}\n\t}\n}\n```\n## 4.二进制状态压缩\n\n二进制状态压缩,是指将一个长度为m的bool数组用一个m位二进制整数表示并存储的方法。利用下列位运算操作可以实现原bool数组中对应下标元素的存取。\n\n\n操作| 运算\n---|---\n取出整数n在二进制表示下的第k位 | (n\u003e\u003ek) \u0026 1\n取出整数n在二进制表示下第0~k-1位(后k位) | n \u0026 ((1\u003c\u003ck)-1)\n把整数n在二进制表示下的第k位取反 | n ^ (1\u003c\u003ck)\n对整数n在二进制表示下的第k位赋值为1 | n \\| (1\u003c\u003ck)\n对整数n在二进制表示下的第k位赋值为0 | n \u0026 (~(1\u003c\u003ck))\n\n这种方法运算简便,并且节省了程序运行的时间和空间。当m不大时,可以直接使用一个整数类型存储。当m较大时,可以使用若干个整数类型(int数组),也可以直接利用bitset实现。\n\n#### 例题3\n给定一张n(n\u003c\u003d20)个点的带权无向图,点从0~n-1标号,求起点0到终点n-1的最短hamilton路径。hamilton路径的定义是从0到n-1不重不漏地经过每个点恰好一次。([洛谷1171](https://www.luogu.org/problemnew/show/P1171),扩展题目:[POJ2288 Islands and Bridges](http://poj.org/problem?id\u003d2288))\n\n思路点拨: \n很容易想到一种朴素的做法,就是枚举n个点的全排列,计算路径长度,取最小值,时间复杂度为O(n*n!),可以使用状态压缩dp将其优化到O(n^2^*2^n^)\n\n在任意时刻,要表示出哪些点被走过,哪些点没有被走过,可以用一个n位二进制数,若其第i位(0\u003c\u003di\u003cn)为1,则表示第i个点已经被经过,反之未被经过。在任意时刻还需要知道当前所处的位置,因此使用F[i,j](0\u003c\u003di\u003c2^n^,0\u003c\u003dj\u003cn)表示点被经过的状态对应的二进制数为i,且目前处于点j时的最短路径。\n\n初始值F[1,0],即只经过了点0(i只有第0位是1),目前处于起点0,最短路径长度为0。方便起见,将F的其他值设为极大值,目标状态为F[(1\u003c\u003cn)-1,n-1],即经过所有点(i的所有位都是1),处于终点n-1的最短路。\n\n在任意时刻,有公式F[i,j]\u003dmin{F[i ^ (1\u003c\u003cj),k]+weight(k,j)},0\u003c\u003dk\u003cn并且((i\u003e\u003ej)\u00261)\u003d1,即当前时刻“被经过的点的状态”对应的二进制数为i,处于点j。因为j只能恰被经过1次,所以一定是刚刚经过的,故在上一时刻“被经过的点的状态”对应的二进制数的第j位应该赋值为0,也就是i^(1\u003c\u003cj)。另外,上一时刻所处的位置可能是i^(1\u003c\u003cj)中任意一个是1的位置k,从k走到j需要weight(k,j),可以考虑取所有这样的k取最小值。\n\n```cpp\nint f[1\u003c\u003c20][20];\nint main()\n{\n\tmemset(f,0x3f,sizeof f);\n\tf[1][0]\u003d0;\n\tfor(int i\u003d1;i\u003c(1\u003c\u003cn);i+\u003d2) \n\t{\n\t\tfor(int j\u003d0;j\u003cn;j++)\n\t\t{\n\t\t\tif(!((i \u003e\u003e j) \u0026 1)) continue; //当前i状态下,根本没有走过j\n\t\t\tfor(int k\u003d0;k\u003cn;k++)\n\t\t\t{\n\t\t\t\tif(j\u003d\u003dk) continue;\n\t\t\t\tif(!(i\u003e\u003ek \u0026 1)) continue; //上一次状态,根本没有走过k,就更不可能从k转移到j\n\t\t\t\tf[i][j]\u003dmin(f[i][j],f[i^(1\u003c\u003cj)][k]+weight[k][j]);\n\t\t\t}\n\t\t}\n\t}\n\tcout \u003c\u003c f[(1\u003c\u003cn)-1][n-1]; // 所有点走完,最后停在n-1点上\n}\n```\n\n## 5.优先级\n\n首先,建议在不清楚优先级的情况下加括号 \n其次,大小关系比较要优于\u0026,|,^,\u003cfont color\u003d\"red\" size\u003d3\u003e **加括号** \u003c/font\u003e \n优先顺序表,从上到下,依次降低\n运算 | 运算符\n---|---\n加减 | +、-\n移位 | \u003c\u003c、\u003e\u003e\n比较大小 | \u003e、\u003c、\u003d\u003d、!\u003d\n位与 | \u0026\n异或 | ^\n位或 | |\n\n\n\n\n\n\n\n\n\n","threadId":39225,"likeCnt":5,"createTime":1542510380000,"isWorkbook":false,"viewCnt":2992,"openness":2,"fav":false,"id":733,"trustable":false}