位图数据结构其实并不是一个全新的玩意,我们可以简单的认为就是个数组,只是里面的内容只能为0或1而已(二进制位数组)。
GETBIT
用于返回位数组在偏移量上的二进制位的值。值得我们注意的是,GETBIT
的时间复杂度是O(1)
。
GETBIT
命令的执行过程如下:
-
计算 (即
>>3
),byte 值表示指定的 位于位数组的哪个字节(计算在第几行); -
指定 中的了,接下来就要计算在8个字节中的第几位呢?使用 计算可得;
-
根据 和 在位数组中定位到目标值返回即可。
BITCOUNT
命令用于统计给定位数组中值为1的二进制位的数量。功能似乎不复杂,但实际上要高效地实现这个命令并不容易,需要用到一些精巧的算法。
1. 暴力遍历
2.查表法
3.二进制位统计算法:variable-precision SWAR文章来源:https://www.toymoban.com/news/detail-618305.html
目前已知效率最好的通用算法为variable-precision SWAR
算法,该算法通过一系列位移和位运算操作,可以在常数时间(这就很牛逼了🐂😍)内计算多个字节的汉明重量,并且不需要使用任何额外的内存。文章来源地址https://www.toymoban.com/news/detail-618305.html
到了这里,关于redis之Bitmap的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!