思路欣赏 - 依旧的博客

思路欣赏

欣赏好的思路是一件愉快的事，特别是对我不会做的题目。

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

Feedback

# re: 思路欣赏 2006-06-23 18:54 E398

没有看明白,但在看完了以后,会想说,这样的想法,能帮助我们解决哪些问题? 回复更多评论

# re: 思路欣赏 2006-06-23 20:44 zliner

确实没有太直接的用处，训练思维吧回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 用例分析基础 MFC的五种基本机制思路欣赏几种排序方法的实现多线程通信的机制 COM基本概念和COM模型排序的方法数据库范式及其涵义 C/S通信和Winsock编程论面向对象

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

依旧的博客

常用链接

留言簿(3)

随笔分类(15)

随笔档案(17)

文章分类(9)

文章档案(1)

搜索

最新评论

阅读排行榜

评论排行榜

Feedback