算法：計算十進制數字在二進制表示1的個數，

題目一

計算十進制數字在二進制表示 1 的個數

舉個例子:

十進制數字為 1 時，它的二進制表示是 001，二進制表示 1 的個數為 1；

十進制數字為 2 時，它的二進制表示是 010，二進制表示 1 的個數為 1；

十進制數字為 3 時，它的二進制表示是 011，二進制表示 1 的個數為 2；

十進制數字為 4 時，它的二進制表示是 100，二進制表示 1 的個數為 1；

十進制數字為 5 時，它的二進制表示是 101，二進制表示 1 的個數為 2；

十進制數字為 6 時，它的二進制表示是 110，二進制表示 1 的個數為 2；

十進制數字為 7 時，它的二進制表示是 111，二進制表示 1 的個數為 3；

時間復雜度 O(logn) 的解法

對于這個題目比較容易想到的是如下代碼：

int count = 0;

while(n != 0)

{

if(n % 2 == 1)

{

count++;

}

n = n >> 1;

}

上述代碼主要做了兩個步驟：

n % 2 表示對數字求模運算，也就是計算二進制的末尾是 1 還是 0，如果二進制的末尾是 1 ，則 count 自增，count 表示的是二進制表示 1 的個數；

n = n >> 1 表示把二進制往右移走一位，比如十進制數字 7 的二進制表示是 111 ，那么通過右移一位后，則變成 011。

這個解決方式雖然能計算出二進制表示 1 的個數，但是我們可以發現這個解法的時間復雜度是 O(logn)，比如當 n 為 7 時，它的二進制表示是 111，那么它將會循環 3 次，也就是非常接近 log 以 2 為底 7 的對數的值。

題目二

程序讀入一個整數 n，假設 n 不會大于 1000，請輸出 1 到 n 每個數字的二進制表示 1 的個數。

時間復雜度 O(nlogn) 的解法

可能有的小伙伴說，這題目二還不簡單？直接把上面的解法，增加個 for 循環不就得了。

int main()

{

int i, j, n, count;

scanf("%d", &n);

for(i = 1; i <= n; i++)

{

j = i;

count = 0;

while(j != 0)

{

if(j % 2 == 1)

{

count++;

}

j = j >> 1;

}

printf("number:%d, count:%d\n", i, count);

}

return 0;

}

假設輸入 7，則輸出結果：

number:1, count:1

number:2, count:1

number:3, count:2

number:4, count:1

number:5, count:2

number:6, count:2

number:7, count:3

number:8, count:1

沒錯，用上述的解法增加個 for 循環，確實可以解決題目二的要求，這值得鼓勵，但是程序的時間復雜度是時間復雜度 O(nlogn) ，運行效率不高，所以我們必須要有種精神，就是要用時間復雜度最少的方式去解決算法的問題，這樣才能一次一次的進步。

時間復雜度 O(n) 的解法

請先觀察下面的位運算性質：

y = x & (x - 1)

我們看到，x 和與 x -1 這兩個數字做按位與運算，所以我們要以二進制的角度去思考這個問題。

比如：

假設 x 是 3，它的二進制是 011；

那么 x - 1 就是 2，它的二進制是 010；

x & (x - 1) 運算后的二進制就是 010。

那么 x & (x - 1) 實際效果等效于去掉 x 二進制表示中的最后一位 1，從而我們發現原來 y 變量與 x 變量在二進制表示中，只差一個 1。

如果我們用一個數組 f 記錄相應數字二進制表示中 1 的數量，那么 f[i] 數組存放的值是 i 這個數字二進制表示中 1 的數量，從而我們可以推導得到 f[i] = f[i & (i - 1)] + 1，也就是說 i 數字比 i & (i - 1) 數字的二進制表示中的 1 的數量要多一個，這樣我們通過一步計算就得到 f[i] 的結果，也就是相應數字二進制表示中 1 的數量結果。

代碼如下：

int main()

{

int n,i;

int f[1001];

f[0] = 0;

scanf("%d", &n);

for(i = 1; i <= n; i++)

{

f[i] = f[i & (i - 1)] + 1;

}

for(i = 1; i <= n; i++)

{

printf("%d ", f[i]);

}

printf("\n");

return 0;

}

這個程序的過程如下：

首先先讀入一個整數 n，代表要求解的范圍;

然后循環 n 次，每一次通過 f[i] = f[i & (i - 1)] + 1 計算得到 f[i] 的值，也就是數字的二進制表示 1 的個數;

最后輸出 1 到 n 中每個數字二進制表示中 1 的個數。

針對這個解法，程序的時間復雜度是 O(n)。

http://www.dengb.com/Cyy/1390440.htmlwww.dengb.comtruehttp://www.dengb.com/Cyy/1390440.htmlTechArticle算法：計算十進制數字在二進制表示1的個數， 題目一 計算十進制數字在二進制表示 1 的個數 舉個例子: 十進制數字為 1 時，它的二進制表...

總結

以上是生活随笔為你收集整理的c语言x在二进制表示下1的个数,算法：计算十进制数字在二进制表示1的个数，...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。