依旧的博客

技术学习

C++博客 首页 新随笔 联系 聚合 管理
  17 Posts :: 1 Stories :: 2 Comments :: 0 Trackbacks
欣赏好的思路是一件愉快的事,特别是对我不会做的题目。

1. 问题:对32位的二进制整数,不用循环,求出其中1的个数。

#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;
}

基本的想法是把所有的1加起来,得到的就是1的个数。我们需要把这些1分离出来,每个1都是平等的,与其位置无关。难题在于不能一个一个去取,那就用到了循环,当然递归也是不允许的。需要有一种统一的办法,可是很难想象具体该怎样。我们逐步地做这件事,假设前16位和后16位分别求得了1的个数,那么加起来就行了。16位二进制中的1仍然是未知的,随机出现的,问题的性质没有变,但我们可以继续分解,这种逐步的做法不一定就意味着递归。每个16位分解为两个8位,...,每个2位分解为两个1位,把两个1位上的数相加就是这两位上1的个数。现在需要取出每一位上的数吗?如果想到了这个问题,就离最终的思路不远了。现在32位已经分成了16个两位,很容易将其看作两个16位,一个是所有奇数位,一个是所有偶数位。我们不难把这两个16位分开,然后移位相加,就求出了每两位中1的个数。到了这一步,以后的思路就很自然了。


参考:

《计算二进制位'1'的个数》来自 http://kaikai.cnblogs.com
posted on 2006-05-12 23:14 依旧的博客 阅读(573) 评论(2)  编辑 收藏 引用 所属分类: 编程

Feedback

# re: 思路欣赏 2006-06-23 18:54 E398
没有看明白,但在看完了以后,会想说,这样的想法,能帮助我们解决哪些问题?  回复  更多评论
  

# re: 思路欣赏 2006-06-23 20:44 zliner
确实没有太直接的用处,训练思维吧  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理