計算出二進制數中有多少個1

計算出二進制數中有多少個1

《程式設計之美》這本書被很多計算機專業的學生奉為面試經典， 其中也包括我。早就聽高年級學長說過，面試中的題目有80%取自《程式設計之美》這本書， 掌握了其中的全部算法可以為自己的面試帶來很多的好處。從今天起， 我每天更新程式設計之美上的一個算法， 友善想要學習的童鞋學習。 計算機專業的學生對二進制數應該都不陌生， 二進制就是由連續的有窮的0，1序列組成的數。那麼， 我們的問題就來了， 現在我要統計一個01序列中有多少個1。那麼， 我們應該怎麼求解呢？ 解法1：普通的解法，二進制數中相鄰的兩個數位在十進制書中參在2倍的關系。那麼，我們的算法就出來了， 不斷的對目标十進制數取餘， 如果v%2==1， 那麼證明目前的對應的二進制數位的數值為1；否則為0。算法如下： int count(int v) {     int number = 0;     while(v)     {         if(v%2 == 1)         {             number++;         }         v /= 2;     }     return number; } 學過算法的同學應該不難分析出來，算法的複雜性是O(logv)。 解法2：根據上述的算法， 我們發現上訴程式的收斂過程是目标數不斷的除以2。我們知道，在計算機在運算的時候，對于除法的計算異常的複雜，是以在這裡我們采用位運算。算法如下： int count(long v) {     int number = 0;     while(v)     {         if(v%2 == 1)         {             number++;         }         v >>= 1;     }     return number; } 在這裡， 我們在收斂過程中使用了位運算，提高了運作的速度。但是，因為算法本身沒有發生變化，是以時間複雜度為O(logv)。 解法3：在上述的算法中， 我們的知道， 算法的複雜度就是二進制數的長度，從某種意義上講，我們對二進制進行了一個周遊。進而得到了我們的算法和分析。但是有沒有更好的？在《程式設計之美》中 ， 書中提供了一種更為快捷的算法， 時間複雜度是O(二進制數中1的個數)。 那麼，寫這本書的大神是怎麼想出來的呢？我想思路主要有以下的幾點： （1）從算法的最有複雜度考慮：算法的最優的複雜度當然是O(1)，但是這道題顯然不能， 是以我們想到了下一個算法複雜度O(logN)，這個複雜度是我們第一個解和第二個解的複雜度， 是以我們立馬想到， 再優的算法當然就是在O(m)(m為二進制中的1的個數). （2）有了上面的分析， 那麼我們就要構造出這個算法。想要達到這個算法複雜度， 我們就必須對二進制數進行必要剪枝，所謂剪枝就是減去掉二進制數中的0。那麼怎麼去掉呢？我們來分析以下二進制的構成：                                                             0x1100010101000 在上訴這個二進制數， 我們可以看到0，1交替出現，當我們用這個數減去一個1的時候， 我們發現最這個數最大的影響就是這個數的最後一一個1變為了0， 并且這個1後面全部的0變為了1， 于是我們可以想到對數進行“與”操作， 去掉受影響的部分，這樣下去直到整個目标數變為0.算法複雜度還真就達到了上述的目标複雜度。 算法如下： int count(long v) {     int number = 0;     while(v)     {         v &= (v-1);         number++;     }     return number; } 呵呵， 是不是很爽， 算法的魅力就在這裡，我們可以用各種稀奇古怪的東西對計算的過程進行一系列的優化。