`

对于一个整数大小的bit数组中的非0 位统计的方法--bitcount [转]

阅读更多

对于bit数组中非0位个数统计的方法,请看以下文章

popcount 算法分析

http://www.cnblogs.com/Martinium/archive/2013/03/01/popcount.html

 

该方法的局限在于如果bit位超过64位则无法处理,仅用于unsigned int 的位计算。

如果对超过64/32bit的bit数组进行统计,则将bit区域按照sizeof(int)来切分,依次进行统计。

 

该文中提及到了 9中方法,

  1. iterated_popcnt  (采用对每位进行移位来统计,效率低下)
  2. sparse_popcnt     (采用数学特性进行处理,n&(n-1) 的方法来依次判断1的个数!循环次数=n中位为1的个数)
  3. dense_popcnt      (sparse_popcnt的变种。当提前知道1的个数较多,可以采用取反的操作,减少1的个数,从而采用sparse_popcnt来提供效率)
  4. lookup_popcnt      (该方法以空间换取时间的。将4字节的整数分为4个1字节char来看待,将256种char的bit1数目保存到表中,当计算n的位为1时,分为4个char,依次从表中直接读取1的位数,然后相加获取4字节空间中位为1的总数目)
  5. parallel_popcnt     (不好说清,大家看来源文章)
  6. nifty_popcnt           (不好说清,大家看来源文章)
  7. hacker_popcnt        (不好说清,大家看来源文章)
  8. hakmem_popcnt     (不好说清,大家看来源文章)
  9. assembly_popcnt     (根据处理支持的popcount指令直接计算)
分享到:
评论

相关推荐

    bmp 位图转换(可将24 位t转为16 / 8 / 4 位)

    封装的一个将24BitCount 的bmp 转换为16bitCount 或8bitcount 或4Bitcount类。并保存。此接口只需要输入要转换图片的路径就可以获得转换后图片的bitmap。此接口在兼容各种平台

    BitCounting:快速研究三种计数位数的方法

    第一个实现如下: uint8_t count_bits ( uint32_t n) { uint8_t counter = 0 ; for ( ; n; n>>= 1 ) if (n & 1 ) ++counter; return counter; } 事实证明,这比未排序的数组处理排序的数组要快得多。 ...

    Bitcount & 按位汉明距离:计算向量中的集合位,并计算向量集合之间的按位汉明距离-matlab开发

    此提交提供两个功能: Bitcount - 计算输入数组的每一列中设置的位数,类型转换为位向量。 Bitwise_hamming - 给定两组位向量(每列是一个位向量),计算两组之间所有向量对之间的汉明距离。 后者功能需要前者,但...

    CSBitmap类,可用于储存DIB位图,也可用于储存二维数列,解决二维数列传递不方便的问题,效率比GDI的bitmap高

    //12位色深COLORREF转24位,32位色深(黑白)值 bool ConvertTo1Bit(CSBitmap* DestBmp); //12,24,36位图片转换成1位色深图 DestBmp用于接收数据的DestBmp指针,转换过程中包括自动参数重置 bool ConvertTo12...

    利用Redis统计网站在线活跃用户的方法

    在工作中我们经常遇到这样的需求,要对某个在线网站的活跃用户数量进行统计。这里我们以redis为例,说明一下其实现的过程。 实现方法 在Redis中存在bitmap这种数据类型,这种数据类型是建立在string数据类型之上的。...

    Redis 用法

    -在Redis中,你可以设定对某一个key值进行消息发布及消息订阅,当一个 key值上进行了消息发布后,所有订阅它的客户端都会收到相应的消息。 这一功能最明显的用法就是用作实时消息系统,比如普通的即时聊天,群聊等...

    Redis的bitmap从基础到业务

    编程界的小学生一、位与字节二、string与bitmap三、bitmap的api1、setbit2、bitpos3、bitcount4、bitop4.1、概述4.2、and4.3、or四、利用bitmap完成需求1、统计某用户登录天数2、查看活跃用户总数五、总结 一、位与...

    windows平台上支持BITMAPCOREHEADER、BITMAPINFOHEADER、BITMAPV4HEADER、BITMAPV5HEADER四种类型位图的类库

    //保存m_pbmfh中malloc出来的内存大小,即是capacity//不为0时保证图像是可以处理的 public: enum BmType{NONE=0,CORETYPE,INFOTYPE,V4TYPE,V5TYPE}; public: class reference { //略.. }; public://DibBitmap01...

    leetcode双人赛-algo-practice:问题解决练习

    bitcount:计算一个数中的位数 字节跳动问题: DFS、BFS、TopSort:图的实现 图问题: integer_division:不使用除法运算的除法 两个数字的 GCD hammingwt:计算汉明重量 向量的堆排序 Intbr:整数中断问题 leetcode...

    QT,jpeg解码project(未完成)

    //长度为N的第一个码字的整数值 int NLengthToSymbolsTableIndex[16]; //查表得到第一个长度为N的符号位于符号表的索引 } HUFFMANTABLE[4]; public: int ReadJFIFInfo(const BYTE* const jfifData,int ...

    QT,JPEG解码源代码(已完成)

    //长度为N的第一个码字的整数值 int NLengthToSymbolsTableIndex[16]; //查表得到第一个长度为N的符号位于符号表的索引 } HUFFMANTABLE[2][2]; public: int ReadJFIFInfo(const BYTE* const jfifData,int ...

    Redis中3种特殊的数据类型(BitMap、Geo和HyperLogLog)

    BitMap 就是通过一个 bit 位来表示某个元素对应的值或者状态, 其中的 key 就是对应元素本身,实际上底层也是通过对字符串的操作来实现。Redis 从 2.2 版本之后新增了setbit, getbit, bitcount 等几个 bitmap

    leetcode凑硬币-Arithmatic:算术

    概要的讲解timsort的实现以及timsort的bugs,因为是视频,所以相比论文我觉得更快看得懂,没字幕,听不懂怎么办,没事,演讲者有一个文章重新梳理视频内容 2,Tim peters自己写的论文 二维“有序数组查找” —...

    C++ 读取bmp图片示例程序

    //每个象素所占用的比特位WORD=unsigned short long BytesPerLine;//位图每行数据所占的字节数LONG=long(有符号) bool operator ==(_bmpsize bs) { if(bmpWidth==bs.bmpWidth && bmpHeight==bs.bmpHeight...

    基于java开发的美食社交APP后台源码+项目源码.zip

    签到功能 Bitmap、String SETBIT、GETBIT、BITCOUNT、BITFIELD 位图存储食客签到信息 积分排行榜 Sorted Set ZINCRBY、ZREVRANK、ZREVRANGE 存储食客总积分集合方便排序 附近的人 Geo、Sorted Set GEOADD、GEOREDIUS...

    bmp格式图片的显示

    bmp图片的显示 MFC上的显示,源代码中提供bitcount的判断 1位 4位 8位 等 代码绝对可运行 如有高手指点,感谢万分

    BMP图像文件的读写与显示

    用Visual C++实现的BMP图像文件的读写与显示,非常完美的!

    javalruleetcode-redis-redlock:Redis数据类型的使用场景、Redisson分布式锁

    一、Redis数据类型使用场景 1. 两个小细节 (1)命令不区分大小写,而 key 区分大小写。 (2)help @ 可以快速查看命令。 # 1: 命令不区分大小写,而 `key` 区分大小写 127.0.0.1:6379[2]> set k1 v1 OK 127.0.0.1:...

    sap_solutions

    sap_solutions ModuleShopping-> src / ... Times3Bitcount-> src / Times3Bitcount.java MaxSumDistance-> src / MaxSumDistance.java AdjacentPointsMinDistance-> src / AdjacentPointsMinDistance.java

    创建位图文件

    CCreateBMP(int width,int height,int BKcolorvalue=128,int colortablelng=1024,int bitcount=8); ~CCreateBMP(void); protected: unsigned char *m_databuf; unsigned char *m_imgbuf; long long unsigned...

Global site tag (gtag.js) - Google Analytics