轉(zhuǎn)：http://toutiao.com/a4280977370/

【解法一】

可以舉一個八位的二進制例子來進行分析。對于二進制操作，我們知道，除以一個 2，原來的數(shù)字將會減少一個0。如果除的過程中有余，那么就表示當(dāng)前位置有一個1。以 10 100 010 為例；第一次除以 2 時，商為1 010 001，余為0。第二次除以 2 時，商為101 000，余為1。因此，可以考慮利用整型數(shù)據(jù)除法的特點，通過相除和判斷余數(shù)的值來進行分析。于是有了如下的代碼。

代碼清單 2-1

【解法二】使用位操作

前面的代碼看起來比較復(fù)雜。我們知道，向右移位操作同樣也可以達到相除的目的。唯一不同之處在于，移位之后如何來判斷是否有1 存在。對于這個問題，再來看看一個八位的數(shù)字：10 100 001。在向右移位的過程中，我們會把最后一位直接丟棄。因此，需要判斷最后一位是否為1，而“與”操作可以達到目的。可以把這個八位的數(shù)字與00000001 進行“與”操作。如果結(jié)果為1，則表示當(dāng)前八位數(shù)的最后一位為1，否則為0。代碼如下：

代碼清單 2-2

【解法三】

位操作比除、余操作的效率高了很多。但是，即使采用位操作，時間復(fù)雜度仍為O（log2v），log2v 為二進制數(shù)的位數(shù)。那么，還能不能再降低一些復(fù)雜度呢？如果有辦法讓算法的復(fù)雜度只與“1”的個數(shù)有關(guān)，復(fù)雜度不就能進一步降低了嗎？同樣用 10 100 001 來舉例。如果只考慮和1 的個數(shù)相關(guān)，那么，我們是否能夠在每次判斷中，僅與1 來進行判斷呢？為了簡化這個問題，我們考慮只有一個 1 的情況。例如：01 000 000。如何判斷給定的二進制數(shù)里面有且僅有一個 1 呢？可以通過判斷這個數(shù)是否是2 的整數(shù)次冪來實現(xiàn)。另外，如果只和這一個“1”進行判斷，如何設(shè)計操作呢？我們知道的是，如果進行這個操作，結(jié)果為0 或為1，就可以得到結(jié)論。如果希望操作后的結(jié)果為 0，01 000 000 可以和00 111 111 進行“與”操作。這樣，要進行的操作就是 01 000 000 &（01 000 000 – 00 000 001）= 01 000 000 &00 111 111 = 0。因此就有了解法三的代碼：

代碼清單 2-3

最后，得到解法四：算法中不需要進行任何的比較便可直接返回答案，這個解法在時間復(fù)雜度上應(yīng)該能夠讓人高山仰止了。

【解法四】查表法

代碼清單 2-5

這是個典型的空間換時間的算法，把0~255 中“1”的個數(shù)直接存儲在數(shù)組中，v 作為數(shù)組的下標(biāo)，countTable[v]就是v 中“1”的個數(shù)。算法的時間復(fù)雜度僅為O（1）。在一個需要頻繁使用這個算法的應(yīng)用中，通過“空間換時間”來獲取高的時間效率是一個常用的方法，具體的算法還應(yīng)針對不同應(yīng)用進行優(yōu)化。

轉(zhuǎn)載于:https://www.cnblogs.com/kira2will/p/4472665.html

總結(jié)

以上是生活随笔為你收集整理的转：对于一个字节（8bit）的变量，求其二进制表示中“1”的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。