依旧的博客

技术学习
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 依旧的博客 阅读(639) 评论(2)  编辑 收藏 引用 所属分类: 编程

Feedback

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

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


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