依舊的博客

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

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


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


參考：

《計(jì)算二進(jìn)制位'1'的個(gè)數(shù)》來(lái)自?http://kaikai.cnblogs.com