网站建设优惠上海做网站优化

位图数据结构其实并不是一个全新的玩意，我们可以简单的认为就是个数组，只是里面的内容只能为0或1而已(二进制位数组)。

GETBIT用于返回位数组在偏移量上的二进制位的值。值得我们注意的是，GETBIT的时间复杂度是O(1)。

GETBIT命令的执行过程如下：

1. 计算 (即>>3)，byte 值表示指定的  位于位数组的哪个字节(计算在第几行)；

2. 指定  中的了，接下来就要计算在8个字节中的第几位呢？使用 计算可得；

3. 根据  和  在位数组中定位到目标值返回即可。

BITCOUNT命令用于统计给定位数组中值为1的二进制位的数量。功能似乎不复杂，但实际上要高效地实现这个命令并不容易，需要用到一些精巧的算法。

1. 暴力遍历

2.查表法

 3.二进制位统计算法:variable-precision SWAR

目前已知效率最好的通用算法为variable-precision SWAR算法，该算法通过一系列位移和位运算操作，可以在常数时间(这就很牛逼了🐂😍)内计算多个字节的汉明重量，并且不需要使用任何额外的内存。