variable-precision SWAR算法

lobo · · 651 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

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

有疑问加站长微信联系（非本文作者）