題目描述：

給定一個數字n，統計1～n之間的n個數字的二進制的1的個數

int Nums_Of_Bit_1(int num)?
{
? ? int* number = new int[num];
? ? int pow = 1,before =1;
int count = 0;

? ? for(int i=1; i<=num; i++){
? ? ? ? if (i == pow){
? ? ? ? ? ? before = number[i] = 1;
? ? ? ? ? ? pow <<= 1;
? ? ? ? }
? ? ? ? else{
? ? ? ? ? ? number[i] = number[before] + 1;
? ? ? ? ? ? before += 1;
? ? ? ? }
count += number[i];
? ? }
? ? return count;
}


int main()
{
cout<<Nums_Of_Bit_1(11)<<endl;
return 0;
}


/*


公式：f（n） = f(2^x)+f（k）,不大于f（n）的最大的2的次方，k一定是在前面出現的，
用數組保存起來，可以直接查詢。
舉例f（5） = f（4）+ f（1）(注意2的x次方都是一個1)，而且是最高位
f（5） = 1+f（1），f（6） = 1+f（2） f（7） = 1+f（3）直到f（8） = 1


*/

{
? ? int* number = new int[num];
? ? int pow = 1,before =1;
int count = 0;

? ? for(int i=1; i<=num; i++){
? ? ? ? if (i == pow){
? ? ? ? ? ? before = number[i] = 1;
? ? ? ? ? ? pow <<= 1;
? ? ? ? }
? ? ? ? else{
? ? ? ? ? ? number[i] = number[before] + 1;
? ? ? ? ? ? before += 1;
? ? ? ? }
count += number[i];
? ? }
? ? return count;
}


int main()
{
cout<<Nums_Of_Bit_1(11)<<endl;
return 0;
}


/*


公式：f（n） = f(2^x)+f（k）,不大于f（n）的最大的2的次方，k一定是在前面出現的，
用數組保存起來，可以直接查詢。
舉例f（5） = f（4）+ f（1）(注意2的x次方都是一個1)，而且是最高位
f（5） = 1+f（1），f（6） = 1+f（2） f（7） = 1+f（3）直到f（8） = 1


*/

總結

以上是生活随笔為你收集整理的求1到n ，这n个整数的二进制表示比特1的个数（时间复杂度：O（n））的全部內容，希望文章能夠幫你解決所遇到的問題。

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