注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

计算二进制位'1'的个数[转]  

2010-11-09 04:42:28|  分类: algorithms |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

第三个算法读了半天,此算法的原作者实在太强大了,佩服之。前两个算法十分简单,我主要分析下第三个神级算法的设计原则。原代码中始用了宏,这个不是本人喜爱的,不过这些宏比较简单,不影响阅读。POW宏使用移位运算来计算2的幂,无话可说。MASK是用来产生相应的模具,这个宏是基于什么原理呢?考虑一个n位全为1的比特位序列,我们可以用这个数去除一些奇数,可以制造出一些奇特的"花纹",其中可以分组成下文所示掩码的序列就有宏中所示的规律,只要简单计算一下就可得到。下面是我用1,3,5,7,9…去除生成的,没事拿去玩吧。

11111111111111111111111111111111

01010101010101010101010101010101

00110011001100110011001100110011

00100100100100100100100100100100

00011100011100011100011100011100

00010111010001011101000101110100

00010011101100010011101100010011

00010001000100010001000100010001

11110000111100001111000011110000

11010111100101000011010111100000

11000011000011000011000011000000

10110010000101100100001011000000

10100011110101110000101000110000

10010111101101000010010111100000

10001101001111011100101100000000

10000100001000010000100001000000

01111100000111110000011111000000

01110101000001110101000001110000

01101110101100111110010001010000

01101001000001101001000001100000

01100011111001110000011000110000

01011111010000010111110100000000

01011011000001011011000001010000

01010111001001100010000010100000

01010011100101111000001010010000

01010000010100000101000001010000

01001101010010000111001111100000

01001010011110010000010010100000

01000111110111000001000111110000

01000101011011000111100101110000

01000011001001011100010100110000

01000001000001000001000001000000

00111111000000111111000000110000

00111101001000100110001101010000

00111011010111001100000011100000

00111001101100001010110100010000

00111000000111000000111000000000

00110110100111010000001101100000

00110101001100011101111011000000

00110011110110010001110100100000

00110010100100010110000111110000

00110001010110010111001000010000

00110000001100000011000000110000

00101111000101001001100100000000

00101110000001011100000010110000

00101101000000101101000000100000

00101100000010110000001011000000

00101011000111011010010001100000

00101010001110100000111111010000

00101001010111111010110101000000

00101000100011011111000011000000

00100111110001000101100101110000

00100111000000100111000000100000

00100110010001111100011010010000

00100101100100111111011010010000

00100100111001101010000101110000

00100100001111110110111100000000

00100011100111100000110101010000

00100011000000100011000000100000

00100010011010111001000000100000

00100001110110011110101011010000

00100001010011010000001000010000

00100000110001001001101110100000

00100000010000001000000100000000

00011111110000000111111100000000

00011111010001000110010110010000

00011110110011000000011110110000

00011110010101110011101011000000

00011101111001011101011011100000

00011101011101111011011001010000

00011101000011001011010110000000

00011100101001001011001100000000

00011100001111111000111100000000

00011011110111010010101110000000

00011011011111010110110000110000

00011011001000000011011001000000

00011010110001010111000000010000

00011010011011010000000110100000

00011010000101101101001111110000

00011001110000101101000101000000

00011001011100001110010011110000

00011001001000001111101101000000

00011000110100110000000110000000

00011000100001101110010111110000

00011000001111001001011101110000

00010111111101000000010111110000

00010111101011010010001000000000

00010111011001111101110011100000

00010111001001000010100001110000

00010110111000011111011101100000

00010110101000010011110011010000

00010110011000011110110001100000

00010110001000111111101001110000

00010101111001110101101110110000

00010101101011000000010101100000

00010101011100011110110100110000

00010101001110010000100101000000

00010101000000010101000000010000

00010100110010101011100010000000

00010100100101010011100111100000

-),再也看一下round做的是什么事情,它其实就是把整个bit位分组,先是两个一组。int 32位的话就分成16个组,在每个小组中统计其中1的个数并记录在这个小组的bit位之中(由此想到最初的分组是32组,每个组中的1的个数当然记录在这个组维一的bit位之中,注意分组后bit位只在组内有意义,而与组所在的int的高位还是低位无关,就是说把一个int给拆分了,虽然拆分后的分组在内存中还处在一个连续的地址上,也就是原来int的地址上)。之后再把分组扩大一位,统计新的分组中的1的个数(就是原两相临分组1的个数的和),依此类推,当分组最终合并到只有1个的时候算法就结束了。这个算法的精巧之处在于达到了所谓SIMD(单指令多数据)操作,可以使用一次运算把所有的分组的1的个数统计出来,达到很强的并行性(注意并不是真的硬件并行)。因此这个算法可谓精巧至极,建议仔细分析下。

写一个函数,返回数字中二进制位为'1'的个数。
比如36,化为二进制得到100100,其中有2'1'

方法1:分别判断各个位

int bit_count(unsigned int n)
{
    int count;
    for(count = 0; n; n >>= 1)
    {
        count += n & 1;
    }
    return count;
}


方法2:循环中直接计算1的数量
如何只数'1'的个数?如果一个数字至少包含一个'1'位,那么这个数字减1将从最低位开始依次向高位借位,直到遇到第一个不为'0'的位。依次借位使得经过的位由原来的'0'变为'1',而第一个遇到的那个'1'位则被借位变为'0'
36 d = 100100 b
36-1 d = 100011 b
如果最低位本来就是'1',那么没有发生借位。
现在把这2个数字做按位与:n & n-1的结果是什么?
2
个数字在原先最低为'1'的位以下(包括这个位)的部分都不同,所以结果是保留了其他的'1'位。
36 & 36-1 d = 100000 b
这个结果刚好去掉了最低的一个
'1'

int bit_count(unsigned int n)
{
    int count;
    for(count = 0; n; n &= n - 1)
    {
        count++;
    }
    return count;
}

由于直接跳过'0'位,这个方法比上面的要略微快一些。
本来以为这个应该最快了,不过农夫三拳又给我看了一个:

方法3:并行计算的- -这个太厉害了

#define POW(c) (1<<(c))
#define MASK(c) (((unsigned long)-1) / (POW(POW(c)) + 1))
#define ROUND(n, c) (((n) & MASK(c)) + ((n) >> POW(c) & MASK(c)))

int bit_count(unsigned int n)
{
    n = ROUND(n, 0);
    n = ROUND(n, 1);
    n = ROUND(n, 2);
    n = ROUND(n, 3);
    n = ROUND(n, 4);
    return n;
}

一下子看不明白,先把宏展开来:
POW
是计算2的幂
MASK
很奇怪,一个全1的无符号数字除以2的幂的幂加1
好在打印出来还能看得懂:

MASK(0) = 55555555 h = 01010101010101010101010101010101 b
MASK(1) = 33333333 h = 00110011001100110011001100110011 b
MASK(2) = 0f0f0f0f h = 00001111000011110000111100001111 b
MASK(3) = 00ff00ff h = 00000000111111110000000011111111 b
MASK(4) = 0000ffff h = 00000000000000001111111111111111 b

这些mask分别把32位数字划分为几个部分。每个部分的前一半和后一半分别是全'0'和全'1'
MASK(0)
分为16个部分,MASK(1)分为8个部分,...
ROUND
中对n的处理:(n & MASK) + (n >> POW & MASK)
POW
的值刚好是MASK中连续'0'(或者连续'1')的长度。也就是说ROUND把由MASK分开的n的各个部分中的高POW位和低POW位相加。
为了便于说明,取一个简单的部分:MASK(1)0011
假设n的值为1001,那么ROUND后的结果就是10 + 01 = 11 b,把这个结果赋值给n,这时n的含义由原来的二进制位串变为'1'位的数量。特别的,当ROUND(n, 0)时,把n当作一个32个部分各自'1'位的数量。('0'表示没有'1',而'1'则表示有1'1'
计算完n = ROUND(n, 0)后,n是一个16个部分各自'1'位数量的'数组',这个'数组'的每个元素只有2个二进制位。最大值为2,足够由2个二进制位来表示。
接下来,计算完n=ROUND(n,1)后,n是一个8个部分各自'1'位数量的'数组',这个'数组'的每个元素只有4个二进制位。最大值为4,足够由4个二进制位来表示。(实际只需要3个二进制位)
...
最后一步,计算n=ROUND(n,4)后,n是一个1个部分各自'1'位数量的'数组',这个'数组'的每个元素有32个二进制位。最大值为32,足够由32个二进制位来表示。(实际只需要6个二进制位)
这个代表32位内'1'位数量的32位二进制数也就是我们要求的结果。
是不是说得有点罗嗦了- -

这个方法的好处是只需要5步(log n (n=32)),并且没有循环(或分支),流水线不会被打破。

  评论这张
 
阅读(1607)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017