二进制与位运算

我们都知道，计算机是使用二进制进行存储和计算的。十进制的出现是因为人类有十个手指，比较方便表示十进制；而对于计算机而言，因为计算机要依靠电源，而电源只有通电和断电两种情况，所以二进制就成为了计算机的基础进制。 一道送分题  对于二进制，似乎更多的考题是在初赛，但复赛也会涉及到一些内容，而且也可以运用在生活中。 ## 接下来介绍一下二进制数 对于二进制数，首先要知道二进制是什么。类似于十进制，二进制也是一种进制(废话)，但二进制运算遵循的规则是“进二”而不是我们熟悉的“进十”。 简单来说，二进制基数为 $2$，只有 $1$ 和 $0$ **二进制转十进制** 对于一个二进制数，他的十进制数为从左往右的每一位乘上该位数的 $2$ 次方(从第0位开始)，例如 $101=1*2^2+0*2^1+1*2^0=5$ **十进制转二进制** 把上面的操作反过来，将十进制数除以 $2$ 直到其为 $0$，每位的余数即二进制的每一位。 其他进制也可以用类似的方法进行转换，例题[P1143 进制转换](https://www.luogu.org/problemnew/show/P1143) ## 原码、反码和补码 **原码**，指一个二进制数左边加上符号位后所得到的码，且当二进制数大于0时，符号位为0；二进制数小于0时，符号位为1；二进制数等于0时，符号位可以为0或1。 **反码**：正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位除外。 **补码**：正数的补码与原码相同，负数的补码是其对应正数二进制所有位取反后加1。 在计算机中通常使用补码进行储存。 一道例题(2017tg初赛)  先确定该数是负数，然后还原操作得到 $01010101=85$，结果为 $-85$ ------------ ------------ ## 介绍几种简单的位运算 因为计算机使用的是二进制，自然就有独成一套体系的运算方式，即位运算。 位运算是计算机中最简洁的运算，并且具有很好用的性质，而且用起来还比较快。总而言之，位运算是十分实用的。 ## “<<” “>>” 运算 首先，在这里这东西跟 $cin$ $cout$ 没有什么关系。 在二进制运算中，这东西叫做“左移”“右移”运算，顾名思义，就是将一个二进制数向左或向右移动 $k$ 位，就是给一个数乘 $2^k$ 或者除 $2^k$ (末尾1不计)。 那么这东西有什么用呢？~~这东西快啊~~ ## “~”运算 又称取反运算，就是对一个二进制数按位取反。 对于 $int$ 来说， ~ $x=-x-1$ 那么这东西有什么用呢？~~我也不知道~~ ## “&”运算 “&”运算，即“and” 运算，也是一种逻辑运算符，对于二进制运算来说，“&”运算的意义是对于两个二进制数的每一位，如果这一位都是 $1$ ，那么这一位为 $1$ ，否则这一位为 $0$。 举个例子 10101(21) & 11100(28) = 10100{20} 我们可以用 & 运算判断一个数是奇数还是偶数，当 $x$ 为奇数时， $x$ 二进制下的第 $0$ 位一定是 $1$ ，否则为 $0$ 。我们让 $x$ & $1$，就可以知道 $x$ 的奇偶性了。 ## “|” 运算 即 “or” 运算，也是一种逻辑运算符，对于二进制运算来说，“|” 运算的意义是对于两个二进制数的每一位，如果这两个数此位有一个 $1$ 那么此位就是 $1$，否则为$0$。 举个例子 10101(21) | 11100(28) = 11101(29) 通过对这两个运算的观察，我们可以发现一个规律 - x & y<=x - x | y>=x 根据二进制的性质很容易就可以得出这些结论吧 ## “^”运算 “^”运算，又称“xor”运算，异或运算。定义是对于两个二进制数的每一位，如果相同则为 $0$ ，否则为 $1$。 举个例子 10101(21) ^ 11100(28) = 1001(9) 异或是一个非常神奇的东东 首先显而易见的是一个数异或他自己肯定是得 $0$ 的 其次对于一个形如 $2*n$ 的数 $x$， $x$ ^ $1 =x+1$,而对于一个形如 $2*n+1$ 的数 $x$， $x$ ^ $1 =x-1$ 然后异或运算满足以下交换律 如果 $x$ ^ $y=z$ 那么 $y$ ^ $z=x$ ， $x$ ^ $z=y$ 异或运算还是比较常用到的，简单举两个例子 **例题一** 给你 $n$ 个数，其中只有一个数出现过一次，其余都成对出现，问只出现过一次的那个数是那个数。 原题 [P1469 找筷子](https://www.luogu.org/problemnew/show/P1469) 利用异或的性质 $x$ ^ $x=0$，将所有数异或起来，最后剩下来的那个数就是答案了。 **例题二** 计算 $1$ ^ $2$ ^ $3$ ^ $4$ ^$...$ ^ $n$ 的值 原题 [P3908 异或之和](https://www.luogu.org/problemnew/show/P3908) 首先最开始是 $1$ ，根据异或的性质，我们可以知道 $(2*n)$ ^ $1$ 是等于 $2*n+1$ 的 然后得到 $2*n_1$ ^ $2*n+1=0$ $0$ ^ $2*n+2=2*n+2$ $(2^n+2)$ ^ $(2^n+3)=1$ 于是我们又回到了 $1$，所以可以得出答案是以 $4$ 为周期循环的。 ------------ ------------ **接下来厉害的来了，这三种运算是可以互相转换的** $x|y=$ ~ $(($~$x)$ & $($~$y))$ $x$ & $y=$ ~ $(($~$x)|($~$y))$ $x$ ^ $y=(x|y)-(x$ & $y)=x+y-((x$ & $y)<<1)$ ~~但这东西似乎除了能让你感受到位运算的博大精深以外似乎什么用都没有~~ ## 运算符的优先级 一道例题(2007tg初赛)  我猜很多人(其实是我)在做这道题的时候果断选了 $18$，然后挂掉了，答案是 $23$ 你可能会懵逼了(其实还是我)：我没算错啊。然后重新算一遍，还是 $18$ 这是因为运算的优先级，本题中会先计算异或运算再计算或运算，也就变成了 $23 | 7=23$ 关于位运算的优先级，大致按下面排序 加减运算 $>$ 移位运算 $>$ 比较大小运算 $>$ 与运算 $>$ 异或运算 $>$ 或运算 如果代码里不注意这些细节可能就会出错 比如对于 $k=2^n-1$ ，如果想用位运算完成，写成 $k=1<<n-1$ 就会是错的 对于拿不准的地方还是加个括号为好 ------------ ## 一些常用的位运算小应用 **快速交换两个数** $x=x$ ^ $y$ $y=y$ ^ $x$ $x=x$ ^ $y$ 这东西理论上能比正常的交换优一点，当然还是用 $swap$ 吧，毕竟人家什么都能换，这个只能换整数。 **lowbit运算** 我们怎样能够快速求出一个二进制数位数最低的 $1$ 在哪呢？ 根据取反运算的性质，$(-x)=($ ~ $x)+1$,设 $x$ 最低的 $1$ 所在位是 $i$， 将 $[0,i-1]$ 全设成 $0$ ，将 $[i+1,31]$ 位全部取反。 所以我们可以得出 $x$ & $(-x)=2^i$ 主要的应用就是树状数组了，这个我不说你们也懂 当然也可以用来计算二进制数中出现了多少个 $1$ **快速判断奇偶性** 这个上面说了，不再多提 **在状压情况下的操作** 先简单介绍一下状压吧。 简单来说就是使用二进制数来表示某一种状态来减少储存的空间，比较常用的有状压 DP 和状压搜索。在洛谷上可以找到例题。 而状压比较常用的操作有（这个图是同学在网上找的，似乎有点小问题?优先级的话大家理性理解吧）  更多奇奇怪怪的应用可视题目要求所定。另外别的进制也可以用来做状态压缩，但是运算起来就没那么方便了，也视情况所定。 **快速幂** 快速幂顾名思义，就是快速算某个数的多少次幂。 求 $x^n$ 的值，我们最朴素的算法是 $O(n)$ 的，而快速幂可以将复杂度优化到 $O(log^n)$ 大致过程是把 $n$ 转换成二进制，判断这一位是 $1$ 还是 $0$，然后进行操作 举个例子 当 $n=11$ 时，$a^{11}=a^{}(2^0+2^1+2^3)$ 大致代码如下 ```cpp int ksm(int a,int b){ int ans=1; while(b){ if(b&1){ ans=ans*a; } b>>=1; a=a*a; } return ans; } ``` **小计算加速** 前面说过了位运算的速度是比四则运算快的，所以可以用来稍稍的加一点速，比如对于整数二分的过程 $ mid=(l+r)/2$ 我们就可以写成 $mid=(l+r)>>1$ 或者在使用线段树的时候 $build(p*2,l,mid);build(p*2+1,mid+1,r)$ 我们可以写成 $build(p<<1,l,mid);build(p<<1|1,mid+1,r)$ 你要相信，这种写法真的不是在嘚瑟，这样真的会快那么一点的，说不定这么一点常数就能让你卡过一道题 ------------ ## **bitset** bitset 是 C++ 里的一个类，我们可以简单认为它就是一个 $01$ 数组，可以对数组的每一位进行赋值，但它还支持很多神奇的操作，比如前面介绍过的位运算，比如 “&” 运算和 “|” 运算，但相比较于用数组完成， bitset 会在时间上占很大的优势。 bitset 在定义的时候一定要定义大小，特殊的是需要使用尖括号，如下。 bitset<1000> $Bitset$ 举一个例子 [P2347 砝码承重](https://www.luogu.org/problemnew/show/P2347) 这道题似乎是一个 DP 题，但巧妙的应用 bitset 的性质也可以完成。 因为 bitset 只能存 $0$ 和 $1$ ，我们可以让第 $i$ 位为 $1$ 来表示可以表示出 $i$ 这个值。 bitset能对某一位赋值，我们初始定义 $Bitset[0]=1$，表示可以表示出 $0$ 当我们加入一个新的砝码的时候，我们将这个砝码加入 bitset ，即进行如下的操作 $Bitset |= Bitset << w[i]$ 简单理解就是已有的所有能表示出的值都加上 $w_i$ 再与原集合取并集。 最后我们统计 bitset 中有多少个 $1$ 即可，可以使用自带函数 $Bitset.count()$ 完成。 bitset 还有一些自带函数，例如 $Bitset.any()$ 返回是否有 $1$ ，$Bitset.set()$ 可以将全部位置赋成 $1$ 等等，大多都是一些二进制操作。 **bitset 的复杂度：**因为bitset是用 uint/long long 类型来实现每次同时操作 32/64 个 01 变量的东西，所以他的很多操作都是 O(1) 或 O(n/32) / O(n/64) 的。至于是 32 还是 64 ，一般看机器是32位还是64位 ------------ ## builtin内置函数 GCC提供了一系列的builtin函数，可以实现一些简单快捷的功能来方便程序编写，简单介绍几种常用的。 有些函数会直接把 $x$ 转成 $unsigned$ 型 ```cpp int __builtin_ctz(x) //返回 x 二进制表示下后导 0 的个数 //带 0 的话会出32 int __builtin_clz(x) //返回 x 二进制表示下前导 0 的个数 //因为转成了 unsigned 带 1 的话是 31，带 2147483648 得 0，不过带 0 还是得 31 int __builtin_ffs(x) //返回二进制下最后一个 1 的位置。 //一般情况下就是 ctz+1 int __builtin_popcount(x) //返回 x 二进制表示下有多少位是 1 int __builtin_parity(x) //返回 x 二进制下 1 的个数的奇偶性。 ``` 以上函数的 $long$ $long$ 版本只需要再函数后面加上 $ll$ 即可 例如 ```cpp __builtin_ctzll(x) ``` 这些函数是 gcc 自带的，不需要额外头文件。 ------------ ------------ 二进制和位运算都属于比较简单的问题，经常活跃在初赛上，而对于复赛则比较基础了，我们更多的是利用二进制的一些性质优化复杂度和完成代码。 ------------ 最后分享一个关于状态压缩的问题，来自于编程之美。 此时象棋棋盘上只剩下双方的将帅，我们知道将和帅是不能面对对方的，请用一个变量表示所有合法的状况。 我们可以使用一个长度为 $18$ 的二进制数，通过把九宫格压成一行，用前九位表示将的位置，后九位表示帅的位置。 有没有更简单的办法呢？ 给九宫格的每一个位置一个标号，可以用两位的十进制数表示将和帅的位置。 你还有别的办法吗？