#include關鍵解法是在 n &= (n – 1) ; 這個地方,為什麼會是這樣寫呢,大家可以想看看,為什麼要 (n-1),其實可以帶數字進去跑看看就知道程式為什麼會這樣寫,這個 case 可以分作兩種,數值可能會有兩種狀況,一種是奇數,另一種就是偶數,8 代表 1000,9 代表 1001,最右邊 bit 是 1 代表奇數,剩下的都是偶數,拿9當例子帶入 while 迴圈試試看,首先將 count + 1,接下來 1001 會跟 1000 做相乘動作,就會變成 1000,接下來跑另一次 while 會變成 1000 & 0111 就會變成 0 了,退出 while 迴圈,所以結論是 (n -1) 的用意是去掉一個 1 位元 bit,就像 [xxxx10 … 0] -1 = [xxxx01 … 1] …. 每運算一次相乘,就會少掉一個 1,原理就是這麼簡單。 這只是一種解法,歡迎大家討論看看還有無其他方法?#include int bitcount(unsigned int); int main(){ int count = 0, a; a = 1023; count = bitcount(a); printf("%d有%d個位元為1\n\n", a, count); system("pause"); return 0; } int bitcount(unsigned int n) { int count = 0 ; while (n) { count++ ; n &= (n - 1) ; //關鍵演算之處 } return count ; }
[C/C++] 計算二進位任意數含有多少個位元為1?
今天看到一個有趣的題目,就是計算二進位任意數值,其中包含了幾個1,這非常有趣,利用每個 bit 做&就可以解出這個問題了: