众所周知，计算机使用二进制进行存储和计算。十进制之所以出现，是因为人类有十个手指，更便于表示十进制。至于电脑，因为电脑依赖电源，而电源只能通电或断电，所以二进制就变成了电脑的基本二进制。
一起发个子问题
对于二进制来说，初赛好像试题比较多，但是复赛也会涉及到一些内容，日常生活中也可以用到。
接下来，我们来介绍一下二进制数。
对于二进制数，我们首先要知道二进制是什么。与十进制类似，二进制也是十进制的一种(无厘头)，但二进制运算的规则是“二进制”而不是大家熟悉的“十进制”。
简单来说，二进制基数是2，只有1和0。
二进制到十进制
对于二进制数，它的十进制数是从左到右的每个数字乘以该数字的二次幂(从第0个数字开始)，例如。
十进制到二进制
把上面的操作反过来，十进制数除以2直到0，每一位的余数就是二进制的每一位。
其他十进制也可以以类似的方式转换，例如P1143十进制转换(https://www.luogu.org/problemnew/show/P1143)
原码、补码和补码
原码是指二进制数左边加符号位得到的码，当二进制数大于0时，符号位为0；当二进制数小于0时，符号位为1；当二进制数等于0时，符号位可以是0或1。
反码：正数的反码与其原码相同；的负代码是对其原始代码的逐位否定，符号位除外。
补码：正数的补码与原码相同，负数的补码是将对应的正二进制的所有位反相后加1。
补码通常用于计算机存储。
一个例子(2017tg预赛)
首先确定数字为负，然后还原操作得到01010101=85，结果为-85。
-
介绍几种简单的位操作。
因为计算机使用的是二进制，自然就有了独特的操作系统，那就是位操作。
位运算是计算机中最简单的运算，使用方便，速度快。总之，位操作非常实用。
" " " "操作
首先，这和CIN库特没有关系。
在二进制运算中，这个东西叫做“左移”和“右移”运算。顾名思义，就是将一个二进制数向左或向右移动k位，也就是将一个数乘以2 k或除以2 k(最后1不算)。
那么这个东西有什么用呢？这东西很快
~”操作
也称为求反运算，是对一个二进制数进行一点一点的求反。
~ x=-x-1表示int
那么这个东西有什么用呢？我也不知道。
" "操作
“”操作，即“与”操作，也是一个逻辑运算符。对于二进制运算，“运算”的含义是，对于两个二进制数的每一位，如果这个位是1，那么这个位就是1；否则，该位为0。
例如
10101(21) 11100(28)=10100{20}
我们可以用运算来判断一个数是奇数还是偶数。当x为奇数时，二进制x的第0位必须为1，否则为0。让x 1知道x的奇偶性。
“|”操作
也就是说，“或”运算也是逻辑运算符。对于二进制运算，“|”运算的意思是，对于两个二进制数的每一位，如果这两个数的这一位有1，那么这一位就是1，否则就是0。
例如
10101(21) | 11100(28)=11101(29)
通过对这两次操作的观察，我们可以发现一个规律。
x y=x
x | y=x
根据二元的性质，很容易得出这些结论。
" "操作
”“运算，又称“异或”运算、异或运算。定义是，对于两个二进制数的每一位，如果相同则为0，否则为1。
例如
10101(21) ^ 11100(28)=1001(9)
或者非常神奇的qpdxz。
首先，很明显，一个数字异或自己一定得到0。
其次，对于形状像2n的数x，x ^ 1=x ^ 1，对于形状像2n ^ 1的数x，x ^ 1=x-1。
那么异或运算满足以下交换定律。
p>如果 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 ，根据异或的性质，我们可以知道 (2n) ^ 1 是等于 2n+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)
大致代码如下
小计算加速
前面说过了位运算的速度是比四则运算快的，所以可以用来稍稍的加一点速，比如对于二分的过程
mid=(l+r)/2
我们就可以写成
mid=(l+r)>>1
或者在使用线段树的时候
build(p2,l,mid);build(p2+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 型
int__builtin_ctz(x)//返回x二进制表示下后导0的个数//带0的话会出32int__builtin_clz(x)//返回x二进制表示下前导0的个数//因为转成了unsigned带1的话是31，带2147483648得0，不过带0还是得31int__builtin_ffs(x)//返回二进制下最后一个1的位置。//一般情况下就是ctz+1int__builtin_popcount(x)//返回x二进制表示下有多少位是1int__builtin_parity(x)//返回x二进制下1的个数的奇偶性。
以上函数的 long long 版本只需要再函数后面加上 ll 即可
例如：
__builtin_ctzll(x)
这些函数是 gcc 自带的，不需要额外头文件。
二进制和位运算都属于比较简单的问题，经常活跃在初赛上，而对于复赛则比较基础了，我们更多的是利用二进制的一些性质优化复杂度和完成代码。
最后分享一个关于状态压缩的问题，来自于编程之美。
此时象棋棋盘上只剩下双方的将帅，我们知道将和帅是不能面对对方的，请用一个变量表示所有合法的状况。
我们可以使用一个长度为 18 的二进制数，通过把九宫格压成一行，用前九位表示将的位置，后九位表示帅的位置。
有没有更简单的办法呢？
给九宫格的每一个位置一个标号，可以用两位的十进制数表示将和帅的位置。
你还有别的办法吗？
本文发布于洛谷日报，特约作者：chengni
原文地址：https://www.luogu.org/blog/chengni5673/er-jin-zhi-yu-wei-yun-suan