一个关于二进制求1的个数的问题

程序名稱： PROGRAM3.EXE 輸入： 標準輸入 輸出： 標準輸出 最長運行時間： 1秒

小明是一個剛學會了二進制數字表示法的學生。他知道每個正整數能以「0」和「1」的數列表示。為了練習所學，他分別把所有從1至N的整數寫成二進制表示，且互不重覆。

請你找出小明從中寫下了多少個「1」。

例如當N = 5，下表展示了從1至N的二進制表示﹕

十進制表示	1	2	3	4	5
二進制表示	1	10	11	100	101
「1」的數量	1	1	2	1	2

從上表可見，當N = 5時，小明總共寫下了7 (=1+1+2+1+2)個「1」。

輸入

輸入僅一行，包含一整數N。

輸出

輸出僅一行，為小明寫下了「1」的次數。

樣例輸入

5

樣例輸出

7

約束條件

對於所有測試數據，

Ø

Ø 1 £ N £ 2⁵⁸

對於50%的測試數據，

Ø 1 £ N £ 100,000

注意事項

如果需要處理大於2³²-1的整數，使用C/C++的參賽者需要使用「long long」（不包括引號）資料型態。以下為使用「long long」作輸入及輸出的樣例﹕

#include "stdio.h"int main(){ long long x; scanf("%I64d", &x); printf("%I64d\n",x); return 0;}

使用Pascal的參賽者需要使用「int64」（不包括引號）資料型態。注意「int64」並非順序型態。以下為使用「int64」作輸入及輸出的樣例﹕

var x : int64;begin readln(x); writeln(x);end.

问题补充 2009-10-20 20:34 问题补充 2009-10-20 20:35

用位运算就可以了。代码如下：

#include "stdio.h"
int main()
{
long long x;
scanf("%I64d", &x);
int count = 0;
while(x!=0)
{
int y = x & 1; //取最低位
if(y == 1) //如果最位为1，计数加1
{
count++;
}
x = x >> 1; //x的二进制向右移一位
}
printf("%d\n",count);
return 0;
}