依舊的博客

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

1. 問題：對32位的二進制整數(shù)，不用循環(huán)，求出其中1的個數(shù)。


基本的想法是把所有的1加起來，得到的就是1的個數(shù)。我們需要把這些1分離出來，每個1都是平等的，與其位置無關(guān)。難題在于不能一個一個去取，那就用到了循環(huán)，當然遞歸也是不允許的。需要有一種統(tǒng)一的辦法，可是很難想象具體該怎樣。我們逐步地做這件事，假設前16位和后16位分別求得了1的個數(shù)，那么加起來就行了。16位二進制中的1仍然是未知的，隨機出現(xiàn)的，問題的性質(zhì)沒有變，但我們可以繼續(xù)分解，這種逐步的做法不一定就意味著遞歸。每個16位分解為兩個8位，...,每個2位分解為兩個1位，把兩個1位上的數(shù)相加就是這兩位上1的個數(shù)。現(xiàn)在需要取出每一位上的數(shù)嗎？如果想到了這個問題，就離最終的思路不遠了。現(xiàn)在32位已經(jīng)分成了16個兩位，很容易將其看作兩個16位，一個是所有奇數(shù)位，一個是所有偶數(shù)位。我們不難把這兩個16位分開，然后移位相加，就求出了每兩位中1的個數(shù)。到了這一步，以后的思路就很自然了。


參考：

《計算二進制位'1'的個數(shù)》來自?http://kaikai.cnblogs.com