进行枚举
通过移位操作，可以创建互不干扰（比特位置不一样）的变量
type1 = 1 type2 = 1 << 1 type3 = 1 << 2 type4 = 1 << 5
最常见的例子，莫过于在LInux系统中的权限信息了，一般说的777、711、700这些都是位运算运用的结果，由于Linux权限是由三个数字组成的，每1个数字都可以包含三个权限信息读、写、执行
exc = 1 # 执行 write = 1 << 1 # 写入 read = 1 << 2 # 读取
在定义出权限值后，我们就可以根据这些权限值来进行组合权限
相加/相减
根据位运算来进行权限的相加和相减
read_exc = exc | read # 5 read_exc_write = exc | read | write # 7
通过或运算符|可以将不同的权限加起来，而搭配使用与运算符&和取反运算符~则可以将某一个权限减去
read_exc_write & (~read) # 去掉了read权限 3
通过与运算符&则可以检查是否含有某个权限
read_exc = exc | read # 5 (read_exc & read) == read # True
获取互补碱基
DNA由A、C、G、T四种碱基组成，首先为其赋值，使用二进制形式来进行赋值
A = 0b00 G = 0b01 C = 0b10 T = 0b11
使用异或运算符^可以直接获得对应碱基的互补碱基
mask = 0b11 A ^ mask == T # True G ^ mask == C # True C ^ mask == G # True T ^ mask == A # True
选取kmer
在选取kmer时，大多数是使用字符串切片的方法，这种方法的效率不高，可以选择使用位运算的方法来进行kmer的选取。首先，这里假设你的碱基已经是由上面的0b00、0b01、0b10、0b11进行表示，那么对于一条序列而言，他的表示形式就由AGCTGATGCTGATGGATTAG变成了一组数字形式的表示01231031231031103301，下面就使用这条序列，以k=4为例，进行选取kmer。
A = 0b00 G = 0b01 C = 0b10 T = 0b11 map_base = { 'A':A, 'G':G, 'C':C, 'T':T } seq = 'AGCTGATGCTGATGGATTAG' k = 4 mask = (1 << k * 2) - 1 # 掩码，只保留8个比特位 mask = 0b11111111 kmer_list = [] mer_4 = 0 # 初始化mer_4 for index,s in enumerate(seq,start=1): # 每次碱基进来，都将mer_4左移两位，空出最右边的两位用来放新的碱基 # 然后使用mask掩码保留最后8位，即一个新的4-mer # 对于k=4而言，每一个kmer的值不会大于255 mer_4 = (mer_4 << 2 | map_base[s]) & mask # 当mer_4里面的碱基个数大于等于k个的时候 # 就可以将mer_4保存到kmer_list中 if index >= k: kmer_list.append(mer_4)
对于一个kmer而言，获取他的互补序列，也可以使用异或运算的方法，只是这里不再使用0b11作为掩码，而是使用选取kmer时使用的mask作为掩码。
mask = (1 << k * 2) - 1 kmer ^ mask
获取kmer的反向互补序列
上面的方法我们已经可以获取kmer并且可以获取kmer的互补序列，但一般我们是希望获取kmer的反向互补序列。对于位运算而言，我们第一个互补碱基就不能从右往左放，而是应该从左往右放，这样才能达到反向的目的。
shift = 2 * (k - 1) kmer = 0 for index,s in enumerate(seq,start=1): kmer = (kmer >> 2) | (0b11 ^ map_base[s]) << shift if index >= k: print(kmer)
这里，我们引入了一个新的变量shift，他的值是2*(k-1)，因为，每一个碱基都是由两个比特位来表示的，在放置的时候，首先将kmer右移两位，为下一个kmer留出位置，然后将新的碱基的互补碱基左移shift位，为了将新碱基放到左边空出来的两个位置，最后将两个数字做|运算，这样就可以在选择kmer的反向互补序列了。
bitmap
bitmap是一种利用比特位置来进行去重的一种方法，原理是，将一组数字映射成位置索引，位置上的0或1代表这个数字有无，这样也就是说，记录一个数字的有无只需要一个比特的空间。比如下面这个例子，有一组数字12359，将他们表示到bitmap上就是将，bitmap中的12359位置的值设为1，其他地方设为0。下面使用python实现一下这个bitmap
class Bitmap: """ bitmap """ def __init__(self,max,chunk_size = 32): """ """ self.btimap = [] self.max = max self.chunk_size = chunk_size self.init_bitmap(max) def init_bitmap(self,max): """ 创建一个bitmap """ # 在这里，我们使用分块存储的方案 # python中一个整型数字的所占用内存空间的大小是根据数字大小来动态分配的 # 这里，我们规定一个数字最多存储32个比特位 # | 32位 | 32位 |...| 32位 | 32位 | self.bitmap = [0] * ((max // self.chunk_size) + 1 ) def clear(self): self.btimap = [0] return True def add(self,number): """ 往bitmap中记录一个数字 """ chunk_idx,bit_idx = self._get_number_idx(number) self.bitmap[chunk_idx] |= (1 << bit_idx) def delete(self,number): """ 从bitmap中删除一个数字 """ chunk_idx,bit_idx = self._get_number_idx(number) self.bitmap[chunk_idx] &= ~(1 << bit_idx) def check(self,number): """ 检查这个数字是否在bitmap中存在 """ chunk_idx,bit_idx = self._get_number_idx(number) return bool(self.bitmap[chunk_idx] & 1 << bit_idx) def _get_number_idx(self,number): """ 获取数字在bitmap中的位置 """ # 返回两个值 # 第一个值是在第几个数字 # 第二个是在第几个比特位 if number > self.max: raise ValueError('数字太大了') chunk_idx,bit_idx = number // self.chunk_size, number % self.chunk_size if bit_idx == 0: bit_idx = self.chunk_size return chunk_idx, bit_idx bitmap = Bitmap(100) bitmap.add(1) bitmap.add(80) print(bitmap.check(1)) # True print(bitmap.check(50)) # False bitmap.add(32) print(bitmap.check(32)) # True
从上面的代码和示意图可以发现，bitmap可以做到节省空间的效果，但是其空间是由一组数中最大的一个数字来决定的，这样在存储量较少但含有一个较大的数字时（比如[1,100000]），是不划算的。下面，介绍一个bitmap的优化版本，布隆过滤器。
布隆过滤器
布隆过滤器与bitmap相比，不再是使用数字大小来直接用作索引，而是使用一个散列函数，将一个数字映射成多个索引，也就是说，由几个组合的比特位来记录一个数字是否存在。
从上面的图中可以看到，一个数字被映射到多个比特位，在添加一个数字到bitmap中时，需要根据散列函数，将多个比特位设为1，在检查一个数字是否存在时，则需要一次性检查多个比特位。这种方法虽然摆脱了受个别较大数字的影响，但这种方法具有一定的误差和难以删除数字的困难。理论上，一个数字经过散列函数被散列到多个位置，只需要将其中任意一个位置设为0即可达到将该数字从bitmap删除的目的，但是由于散列函数散列效果并不完美，不同的数字，有可能会产生相同的位置，比如上图中那样，当你删除1这个数字时，将第5个比特位设为0虽然可以将1删除，但与此同时9也被删除了。
