文档章节

Redis——二进制位数组

nao
 nao
发布于 2016/05/27 16:00
字数 508
阅读 585
收藏 0

Redis提供了SETBIT,GETBIT,BITCOUNT,BITOP四个命令用于处理二进制位数组(bit array,又称"位数组").其中,SETBIT命令用于为位数组指定偏移量上的二进制设置值,位数组的偏移量从0开始计数,而二进制位的值则可以是0或者1;
    最后,BITOP命令既可以对多个位数组进行按位与(and),按位或(or), 按位异或(xor)运算。
    也可以对给定的位数组进行取反(not)运算。
    
BITCOUNT 命令的实现的算法:
    1. 遍历算法
    2. 查表算法
    3. variable-precision swar算法(什么鬼,看了一些文章还是不明白)
    
    BITCOUNT命令要解决的问题——统计一个位数组中非0二进制的数量,在数学上被称为"计算汉明重量(Hamming Weight)"。
    因为汉明重量经常被用于信息论,编码理论和密码学,所以研究人员针对计算汉明重量开发了多种不同的算法,一些处理器甚至直接带有计算汉明重量的指令,而对于不具备这种特殊指令的普通处理器来说,目前已经效率很好的通用算法为variable-percision SWAR算法,该算法通过一系列位移和位运算操作,可以在常数时间内计算多个字节的汉明重量,并且不需要使用任何额外的内存。

http://www.cnblogs.com/chenwenbiao/archive/2011/09/12/2174139.html
http://www.yanyiwu.com/work/2014/01/30/simhash-shi-xian-xiang-jie.html


总结:

    Redis使用SDS来保存位数组。

    SDS使用逆序来保存位数组,这种保存顺序简化了SETBIT命令的实现,使得SETBIT命令可以在不移动现有二进制位的情况下,对位数组进行空间扩展。

   BITCOUNT 命令使用查表算法和variable-precision SWAR算法来优化命令的执行效率。

   BITOP命令的所有操作都使用C语言内置的位操作来实现。

© 著作权归作者所有

上一篇: Redis——排序
下一篇: Redis——监视器
nao

nao

粉丝 28
博文 155
码字总数 108154
作品 0
成都
后端工程师
私信 提问
使用 Redis 统计在线用户人数

原文地址 使用 Redis 统计在线用户人数 在构建应用的时候, 我们经常需要对用户的一举一动进行记录, 而其中一个比较重要的操作, 就是对在线的用户进行记录。 本文将介绍四种使用 Redis 对在...

一枼落知天下
01/29
0
0
十五分钟介绍 Redis 数据结构

Redis是一种面向“键/值”对类型数据的分布式NoSQL数据库系统,特点是高性能,持久存储,适应高并发的应用场景。它起步较晚,发展迅速,目前已被许多大型机构采用,比如Github,看看谁在用它...

鉴客
2011/10/08
2.9K
3
【白话经典算法系列之十二】数组中只出现1次的两个数字(百度面试题)

微博http://weibo.com/MoreWindows已开通,欢迎关注。 本系列文章地址:http://blog.csdn.net/MoreWindows/article/category/859207 首先来看题目要求: 在一个数组中除两个数字只出现1次外,...

长平狐
2012/12/10
80
0
Java Connection集合分析之Queue

Queue队列 1.Queue用于模拟队列这种数据结构,队列通常是指“先进先出”(FIFO)的容器。新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。通常,队列不允许随机...

我爱春天的毛毛雨
2018/11/14
0
0
【小知识大道理】被忽视的位运算

Bitwise Operation导语 众所周知计算机是基于二进制01进行运算的,理所当然地,位运算相对于各种算术运算更加贴合计算机的二进制语义,运算效率会更快。这样计算机是舒服了,人类读起来就太生...

曲高和寡_健
2017/11/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Jenkins系列_插件安装及报错处理

进入Jenkins之后我们可以进行插件的安装,插件管理位于以下模块: 发现上面报了一堆错误,是因为插件的依赖没有安装好,那么这一节,就先把这些错误解决掉吧。解决完成后,也就基本会使用插件...

shzwork
今天
2
0
mysql mysql的所有查询语句和聚合函数(整理一下,忘记了可以随时看看)

查询所有字段 select * from 表名; 查询自定字段 select 字段名 from 表名; 查询指定数据 select * from 表名 where 条件; 带关键字IN的查询 select * from 表名 where 条件 [not] in(元素...

edison_kwok
昨天
9
0
多线程同时加载缓存实现

import com.google.common.cache.Cache;import com.google.common.cache.CacheBuilder;import java.util.concurrent.ExecutionException;import java.util.concurrent.ExecutorServi......

暗中观察
昨天
3
0
利用VisualVM 内存查看

准备工作,建几个测试类。等下就是要查看这几个类里面的属性 package visualvm;public class MultiObject { private String str; private int i; MultiObject(String str...

冷基
昨天
2
0
组装一台工作游戏两用机

一、配置清单如下: 分类 项目 价格(元) 主板 华硕(ASUS)TUF Z370-PLUS GAMING II 电竞特工 Z370二代 支持9代CPU 1049 CPU 英特尔(Intel) i7 8700K 酷睿六核 盒装CPU处理器 2640 风扇 九...

mbzhong
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部