分享
  1. 首页
  2. 文章

variable-precision SWAR算法

lobo · · 1095 次点击 · · 开始浏览
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

目的:计算uint32_t二进制数中1的数量

算法实现:

 uint32_t swar(uint32_t i){
		// step 1: 计算出的值i的二进制表示可以按每两个二进制为一组进行分组
		// ,各组的二进制表示该组中1的个数
		i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
		// step 2:计算出的值i的二进制表示可以按每四个二进制为一组进行分组
		// ,各组的二进制表示该组中1的个数
		i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
		// step 3:计算出的值i的二进制表示可以按每八个二进制为一组进行分组
		// ,各组的二进制表示该组中1的个数
		i = (i & 0xOFOFOFOF) + ((i >> 4) & 0xOFOFOFOF);
		// step 4:其中i * (0x01010101)是计算出位数组中1的个数并记录在最高8位,>> 24则是右移24位得到1的个数
		i = (i * (0x01010101) >> 24)
		return i;
	}

举例:
求二进制 0010 0101 0000 1010 1111 0001 1010 0101 中1的个数
step 1:
1.1、 (i & 0x55555555): 0010 0101 0000 1010 1111 0001 1010 0101
0101 0101 0101 0101 0101 0101 0101 0101
------------------------------------------------
结果: 0000 0101 0000 0000 0101 0001 0000 0101

1.2、 ((i >> 1) & 0x55555555): 0001 0010 1000 0101 0111 1000 1101 0010
0101 0101 0101 0101 0101 0101 0101 0101
------------------------------------------------
结果: 0001 0000 0000 0101 0101 0000 0101 0000

1.3、(i & 0x55555555) + ((i >> 1) & 0x55555555):
0000 0101 0000 0000 0101 0001 0000 0101
0001 0000 0000 0101 0101 0000 0101 0000
------------------------------------------------
结果 0001 0101 0000 0101 1010 0001 0101 0101

step 2:
2.1、(i & 0x33333333) :
0001 0101 0000 0101 1010 0001 0101 0101
0011 0011 0011 0011 0011 0011 0011 0011
------------------------------------------------
结果 0001 0001 0000 0001 0010 0001 0001 0001

2.2、((i >> 2) & 0x33333333) :
0000 0101 0100 0001 0110 1000 0101 0101
0011 0011 0011 0011 0011 0011 0011 0011
------------------------------------------------
结果 0000 0001 0000 0001 0010 0000 0001 0001

2.3、(i & 0x33333333) + ((i >> 2) & 0x33333333) :
0001 0001 0000 0001 0010 0001 0001 0001
0000 0001 0000 0001 0010 0000 0001 0001
------------------------------------------------
结果 0001 0010 0000 0010 0100 0001 0010 0010

step 3:
(i & 0xOFOFOFOF) + ((i >> 4) & 0xOFOFOFOF):
0000 0010 0000 0010 0000 0001 0000 0010
0000 0001 0000 0000 0000 0100 0000 0010
------------------------------------------------
0000 0011 0000 0010 0000 0101 0000 0100

step 4:(i * (0x01010101) >> 24):
0000 0011 0000 0010 0000 0101 0000 0100
0000 0001 0000 0001 0000 0001 0000 0001

利用了内存溢出,精度缺失,把最终值留在了最8高位,相当于每8位相加
0000 0011
0000 0010
0000 0101
0000 0100
结果: 0000 1110 = 14

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

关注微信
1095 次点击
暂无回复
添加一条新回复 (您需要 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传

用户登录

没有账号?注册
或
(追記) (追記ここまで)

今日阅读排行

    加载中
(追記) (追記ここまで)

一周阅读排行

    加载中

关注我

  • 扫码关注领全套学习资料 关注微信公众号
  • 加入 QQ 群:
    • 192706294(已满)
    • 731990104(已满)
    • 798786647(已满)
    • 729884609(已满)
    • 977810755(已满)
    • 815126783(已满)
    • 812540095(已满)
    • 1006366459(已满)
    • 692541889

  • 关注微信公众号
  • 加入微信群:liuxiaoyan-s,备注入群
  • 也欢迎加入知识星球 Go粉丝们(免费)

给该专栏投稿 写篇新文章

每篇文章有总共有 5 次投稿机会

收入到我管理的专栏 新建专栏