variable-precision SWAR算法

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

目的:计算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

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