求1到n ，这n个整数的二进制表示比特1的个数（时间复杂度：O（n））

题目描述：

给定一个数字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


*/