位运算

~      按位取反

<<    左移运算符，num<<1 == num*2

>>    右移运算符，num>>1 == num/2

BitMap 位图

假设欲存储100以内的质数

一个int型整数占4字节，100以内有25个质数，占4*25=100字节。

用位图存储，位数代表该元素，位上的值代表是否有该元素，100以内的数，只需要100位，即100/32+1=4字节。

总结1：需要位图大小，可用 type_name bmp[ N / type_size + 1 ] 计算，其中N代表欲存储的最大值。

bmp[0] 

bmp[1]

bmp[2]

bmp[3]

总结2：给定一个数M，求其行数 M / type_size，求其列数 M % type_size

a_{0 = 0}

插入：放入质数2,2/32=0,2%32=2,即应放入第0行第2列。 a_{1 =} a₀ +2/32 | (1<<2)  = 0000 0000 0000 0000 0000 0000 0000 0100

          放入质数3,3/32=0,3%32=3,即应放入第0行第3列。 a_{2 =} a₁ + 3/32 | (1<<3)  = 0000 0000 0000 0000 0000 0000 0000 1100 

总结3：插入公式： a_n = a_n-1 + (i / type_size) | (1<< (i%type_size))

删除：删除37,   ~ (1 << (37%32) ) 该位置0，其他位置1。 bmp[37/32] &  ~ (1 << (37%32) ) 。

总结3：删除公式： bmp[ i / type_size ] = bmp[ i / type_size ] & ~ (1<< (i%type_size))

查找：查找73存不存在，bmp[73/32] & (1<<73%32) == 1 ? true : false ;

总结4：查找公式：bmp[ i / type_size ] &  (1<< (i%type_size)) == 1 ? true : false 

位运算

原文：https://www.cnblogs.com/tomatokely/p/14764719.html