依舊的博客

技術學習

C++博客

管理

17 Posts :: 1 Stories :: 2 Comments :: 0 Trackbacks

常用鏈接

留言簿(3)

隨筆分類(15)

隨筆檔案(17)

文章分類(9)

文章檔案(1)

2007年5月 (1)

搜索

閱讀排行榜

評論排行榜

思路欣賞

欣賞好的思路是一件愉快的事，特別是對我不會做的題目。

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 依舊的博客閱讀(701) 評論(2) 編輯收藏引用所屬分類: 編程

Feedback

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

沒有看明白,但在看完了以后,會想說,這樣的想法,能幫助我們解決哪些問題? 回復更多評論

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

確實沒有太直接的用處，訓練思維吧回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。


相關文章: 用例分析基礎 MFC的五種基本機制思路欣賞幾種排序方法的實現多線程通信的機制 COM基本概念和COM模型排序的方法數據庫范式及其涵義 C/S通信和Winsock編程論面向對象

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品