免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2874 | 回复: 3

这个算法怎么理解?Counting bits set [复制链接]

论坛徽章:
0
发表于 2011-11-22 16:08 |显示全部楼层
  1. Counting bits set, in parallel

  2. unsigned int v; // count bits set in this (32-bit value)
  3. unsigned int c; // store the total here
  4. static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
  5. static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

  6. c = v - ((v >> 1) & B[0]);
  7. c = ((c >> S[1]) & B[1]) + (c & B[1]);
  8. c = ((c >> S[2]) + c) & B[2];
  9. c = ((c >> S[3]) + c) & B[3];
  10. c = ((c >> S[4]) + c) & B[4];

  11. The B array, expressed as binary, is:

  12. B[0] = 0x55555555 = 01010101 01010101 01010101 01010101
  13. B[1] = 0x33333333 = 00110011 00110011 00110011 00110011
  14. B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111
  15. B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111
  16. B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111

  17. We can adjust the method for larger integer sizes by continuing with the patterns for the Binary Magic Numbers, B and S. If there are k bits, then we need the arrays S and B to be ceil(lg(k)) elements long, and we must compute the same number of expressions for c as S or B are long. For a 32-bit v, 16 operations are used.

  18. The best method for counting bits in a 32-bit integer v is the following:

  19. v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
  20. v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
  21. c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

  22. The best bit counting method takes only 12 operations, which is the same as the lookup-table method, but avoids the memory and potential cache misses of a table. It is a hybrid between the purely parallel method above and the earlier methods using multiplies (in the section on counting bits with 64-bit instructions), though it doesn't use 64-bit instructions. The counts of bits set in the bytes is done in parallel, and the sum total of the bits set in the bytes is computed by multiplying by 0x1010101 and shifting right 24 bits.



复制代码

论坛徽章:
0
发表于 2011-11-23 01:47 |显示全部楼层
本帖最后由 fallening 于 2011-11-23 01:59 编辑

二分
hacker's delight 上有写

论坛徽章:
0
发表于 2011-11-23 09:01 |显示全部楼层
回复 2# fallening


    极品好书阿,谢谢

论坛徽章:
0
发表于 2011-11-23 09:39 |显示全部楼层
不懂呀
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

【架构革新 高效可控】2020年12月21日-23日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP