📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5967| 回复: 12
跳转到指定楼层
上一主题 下一主题
收起左侧

google : 计算二进制1的个数

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
给100万个数(32位整型),设计一个方案来计算着100万个数含二进制1的个数,综合时间和空间复杂度的考量

上一篇:Google : 找丑数
下一篇:Amazon : 设计一个并行运算的程序
🔗
Etrnls 2011-4-28 19:04:58 | 只看该作者
全局:
什么意思?比如523里面有4个1?
回复

使用道具 举报

🔗
Imbalism 2011-4-28 21:08:15 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-5-1 23:39 编辑

以前做过,
大概分3种把,
第一种迭代式,每次n && n - 1,count++,直到n为0
第二种预处理好几个bit,8bit或者16bit,然后把每个整形套进去。
第三种是并行的形式,当时没看懂,这次刚好借这个机会再复习一遍。
回复

使用道具 举报

🔗
Etrnls 2011-4-28 21:41:58 | 只看该作者
全局:
回复 3# Imbalism

并行的是指这个么?

int popcount(uint32_t x)
{
        static const uint32_t k1 = 0x55555555;
        static const uint32_t k2 = 0x33333333;
        static const uint32_t k4 = 0x0f0f0f0f;
        static const uint32_t kf = 0x01010101;

        x = x - ((x >> 1) & k1);
        x = (x & k2) + ((x >> 2) & k2);
        x = (x + (x >> 4)) & k4;
        x = (x * kf) >> 24;
        return x;
}
回复

使用道具 举报

🔗
darksteel 2011-4-29 00:20:30 | 只看该作者
全局:
。。这题好像也在careercup上有,lss已经总结的灰常全面了。GCC里有内建函数可用:__builtin_popcount。据说这题有好些非常巧妙的并行做法,ls的看着就很不错
回复

使用道具 举报

🔗
kinslover 2011-4-30 11:58:59 | 只看该作者
全局:
只想到了逐位查的人捂脸飘过T..T
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-1 23:02:18 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-5-1 23:40 编辑

以前做过,
大概分3种把,
第一种迭代式,每次n && n - 1,count++,直到n为0
第二种预处理好几个bit,8bit或者16bit,然后把每个整形套进去。
第三种是并行的形式,当时没看懂,这次刚好借这个机会再复习一遍。
Imbalism 发表于 2011-4-28 21:08


标答是第二种。


并行的因该可以综合第二种解决方案。我想一种哈,不知道合不合理:
假设是a[n], 有m个处理器 (n>>m)

1. spawn int k = m*2-2 个线程
2. 设置一个计数器Iter,这个计数器的操作对必须是线程安全的
线程安全函数 : int GetAndIncIter().
3. 线程函数 :
void ThrdFunc(void * p)
{
   ......
    for (....)
    {
         int x =  GetAndIncIter();
         计算a[x]里1的个数 ==> res
         总结果 += res. //这个过程同样是线程安全的
     }
}

这里一次计算一个可以改为一次计算几个以减少 加锁-释放 的开销
回复

使用道具 举报

🔗
Etrnls 2011-5-1 23:48:37 | 只看该作者
全局:
回复 7# wwwyhx

你这样并行就不好玩了……

如果一个问题是:分别求n个xxx的yyy,那总归可以开多个线程并行跑,因为这个n的东西是独立的,但是你这个开多个线程跑并没有解决每个独立的问题:求1个xxx的yyy怎么做,也就是你说的"计算a[x]里1的个数 ==> res"这个“计算”是怎么完成的。

Imbalism说的方法都是解决独立的问题的方法。对于这个问题而言,我认为解决独立的问题相对于解决100万个的问题更有意义:独立的问题有更好的方法,100万个的问题也自然更好。

“解决100万个独立问题”是个单独的问题,我完全可以出道题,问你100万个数求平方和怎么做,100个数求回文数的个数一共多少,100个数blablabla……,那你首先要解决,1个数怎么求平方?1个数怎么判断回文?然后再解决,怎么解决100万的问题,比如并行跑很多线程分别求独立问题……

对于这个题而言,所谓的并行的算法仍然是针对独立问题而言的。
逐位枚举的方法之所以慢,是因为没有充分利用现在32位计算机的计算能力,一次只算了一个bit
那现在我们这样做,对于两个bit数x,比如这两个bit叫a, b (i.e. x = a * 2 + b),那么x - a就得到了x里面1的个数(x - a = a * 2 + b - a = a + b),那对于32bit的数x,x - x & 0x55555555就得到了一个数y,这个数的每两bit表示的数都分别是相应那两bit里面1的个数,然后继续对折相加最终就可以得到结果了。按照这个方法可以以O(logW)的时间复杂度计算一个W bit数的1的个数。对于一些乘法指令和加法差不多快的机器,不断对折相加的过程可以用一个乘法代替,于是算法的步骤就更少了。

P.S.: 具体问题具体分析,查表的算法需要更多的内存访问+导致更多的cache失效,究竟查表快还是计算快不能一概而论,不存在所谓标答。

评分

参与人数 1大米 +100 萝卜 +5 收起 理由
wwwyhx + 100 + 5

查看全部评分

回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-2 00:15:11 | 只看该作者
全局:
回复  wwwyhx

你这样并行就不好玩了……

如果一个问题是:分别求n个xxx的yyy,那总归可以开多个线程并行跑,因为这个n的东西是独立的,但是你这个开多个线程跑并没有解决每个独立的问题:求1个xxx的yyy怎么做,也就是你说的"计算a[x]里1的个数 ==> res"这个“计算”是怎么完成的。

Imbalism说的方法都是解决独立的问题的方法。对于这个问题而言,我认为解决独立的问题相对于解决100万个的问题更有意义:独立的问题有更好的方法,100万个的问题也自然更好。

“解决100万个独立问题”是个单独的问题,我完全可以出道题,问你10 ...
Etrnls 发表于 2011-5-1 23:48


我了个去,没仔细看,我还以为"并行"算法是multi-thread呢

不过我感觉bitmap的解决方案还是快些
1.把n个数看作2n个16位的话,这个map所需空间仅为256kb,我认为这么大点空间不至于让操作系统产生thrashing的现象(排除其他因素吃掉内存的情况),毕竟经常访问的页面是常驻内存的。
2. 那个算法挺复杂的,没仔细看。4行代码,每行有好几个操作,觉得没有直接map获取答案的快,操作的少
回复

使用道具 举报

🔗
Etrnls 2011-5-2 00:39:00 | 只看该作者
全局:
回复 9# wwwyhx

关键是你要频繁做访存,你又不能保证你的查表的表一定在cache里,只要有一次访问它不在cache里,嘿嘿,访问内存需要的时钟周期可是比加加减减神马的多几个数量级的哦。
这东西必然要到实际机器上跑一跑测一测的,究竟哪个效率更好从体系结构到操作系统都关系很大的。

有的cpu里面有专门的指令用来算popcount的,感觉上那一定超级快吧?有人测试过,sometimes没有并行的算法快,虽然看上去指令数更多,但是消耗的时钟周期却更少。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表