1.位运算
位运算
- 按位与 : & ,and （有0为0，无0为1）
- 按位或：|，or （有1为1，无1为0）
- 异或：^,xor （相同为0，不同为1）
- 非：~，not （取反）
m位二进制，通常最低位为第0位
移位运算
1<< n=2^n^
n<<1 = 2n
n>>1 = floor(n/2.0) 除以2向下取整
二进制状态压缩
注意下表的第k位都是从第0位开始的
更多状压DP请点击下方链接：
https://blog.csdn.net/weixin_45697774/article/details/104874248
成对变换
lowbit
lowbit定义为非负整数n在二进制表示下“最低位的1及其后边的所有0”构成的数值， 例如n=10=(1010)2,则lowbit(n) = 2 =(10)2 ,
-x 的值， 其实就是在x的值的基础上进行按位取反(x)之后在增加1所得, x & -x == x & (x + 1)
x&(-x) , 如果是x是奇数， 那x & -x 的结果一定是1 ; 当一个偶数与它的负值相与时， 结果是能整除这个偶数的最大的2的幂, 即： m = n & -n , 则 n % m = 0, 且 m = 2 ^ k
lowbit配合hash可以找出整数二进制表示下的所有的是1 的位数。
位图
vector of bits也就是位图，由于可以用非常紧凑的格式来表示给定范围的连续数据而经常出现在各种算法设计中，这里非常紧凑的格式指的就是数组。
基本原理是，在一个特定的位置上(往往是数组下标的位置上)的值(开关)，0为没有出现过，1表示出现过，也就是说使用的时候可根据某一个位置是否为0表示此数(这个位置代表的数，往往是下标)是否出现过。
为了方便大家理解，我么可以对上图的数据解释一下，上图是我截取了一个位向量的一部分，也就是下标为1000-1009 的位置。这里开关为1(值为1)代表着此处的数据出现过，也就是说值为数组下标的数据，也就是1000出现过，同理1003 也出现过，然后就是1008 也出现过，其他的都没有出现过。
其实到这里我们就可以对位图有了一个基本的认识，说白了它就是用数组表示特定位置上的数据出现过没有，因为出现还是没有出现只会有两种结果，也就是true 和 false ，所以我们可以使用0 1 来表示，这里的0 1 指的是二进制中的0 1 ，这样我们用bit 来表示，而不是使用其他数据类型，例如Int 类型或者是String ,因为这种数据类型是比较耗空间的，这就是为什么我们使用这种数据结构的原因
BitSet类
BitSet类实现了一个按需增长的位向量,实际是由“二进制位”构成的一个Vector。每一位都是一个表示true或者false 的boolean 值。如果我们希望高效地存储这样只有两种类型的数据，就可以使用BitSet。
首先需要说明的是，BitSet并不属于集合框架，没有实现List或Map或者Set接口，BitSet更多的表示一种开关信息，对于海量不重复数据，利用索引表示数据的方式，将会大大节省空间使用。
面试题
面试题中也常出现，比如：统计40亿个数据中没有出现的数据，将40亿个不同数据进行排序等。
又如：现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来(百度)。
programming pearls上也有一个关于使用bitset来查找电话号码的题目。
Bitmap的常见扩展，是用2位或者更多为来表示此数字的更多信息，比如出现了多少次等。
相关习题
https://fanfansann.blog.csdn.net/article/details/105595549
微信打赏