Recurrence Relation : How many 1's between 0 to n

Explain:
we know,
Total Number of 1 bit between 0 to 2^n-1
On = 2^(n-1) + 2*On-1 [Read: Recurrence Relation : How many 1's between 0 to (2^n-1) ]
Vn = 2^n -1 

Now,
1. Given n and let T1 = 0
2. Nn = n
3. find i, where v[i]>Nn
4. T1 = o[i-1]
5. MSB_ONE = Nn - v[i-1];
6. T1 = T1+MSB_ONE;
7. Now new, Nn = MSB_ONE-1;
8. break if Nn<=0; otherwise go to step3



Example:
Find Total Number of 1 bit between 0 to 12 = ?

 

O3 = 12 , V3 = 7 , 
MSB_ONE = V3 - O3
MSB_ONE = 12-7 = 5, Nn = MSB_ONE -1 = 4

T1 = 0+O3+MSB_ONE = 0+12+5 = 17 (Proved: Look at the above figure)

Now Our Problem range is [0,4]

O2 = 4 , V2 = 3 , 
MSB_ONE = V3 - O3
MSB_ONE = 4-3 = 1, Nn = MSB_ONE -1 =0

T1 = 0+O3+MSB_ONE = 17+4+1 =22 (Answer)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include<stdio.h> typedef unsigned long long int64; int main(){ int64 O[65],V[65],two,n,Nn,T1=0,msb_one; int i; O[1]=1; V[1]=1; two = 1; for (i=2;i<64;i++){ two = two<<1; O[i] = two + 2*O[i-1]; V[i] = (two<<1)-1; printf("O[%d]= %llu V[%d]: %llu\n",i,O[i],i,V[i]); } printf("Enter 0 to break\n"); while(1){ scanf("%llu",&n); if (n==0) break; T1 = 0; Nn = n; while(Nn>0){ for(i=1;;i++){ if(V[i]>Nn) break; } i = i-1; T1=T1+O[i]; msb_one=(Nn-V[i]); T1=T1+msb_one; if( msb_one == 0) break; /*safty Purpose: Usigned Nn*/ Nn=msb_one-1; } printf("Total Number of 1's between 0 to %llu : %llu\n",n,T1); } return 0; }

 Sample Output:
---------------------
O[2]= 4 V[2]: 3
O[3]= 12 V[3]: 7
O[4]= 32 V[4]: 15
O[5]= 80 V[5]: 31
O[6]= 192 V[6]: 63
O[7]= 448 V[7]: 127
O[8]= 1024 V[8]: 255
O[9]= 2304 V[9]: 511
O[10]= 5120 V[10]: 1023
O[11]= 11264 V[11]: 2047
O[12]= 24576 V[12]: 4095
O[13]= 53248 V[13]: 8191
O[14]= 114688 V[14]: 16383
O[15]= 245760 V[15]: 32767
O[16]= 524288 V[16]: 65535
O[17]= 1114112 V[17]: 131071
O[18]= 2359296 V[18]: 262143
O[19]= 4980736 V[19]: 524287
O[20]= 10485760 V[20]: 1048575
O[21]= 22020096 V[21]: 2097151
O[22]= 46137344 V[22]: 4194303
O[23]= 96468992 V[23]: 8388607
O[24]= 201326592 V[24]: 16777215
O[25]= 419430400 V[25]: 33554431
O[26]= 872415232 V[26]: 67108863
O[27]= 1811939328 V[27]: 134217727
O[28]= 3758096384 V[28]: 268435455
O[29]= 7784628224 V[29]: 536870911
O[30]= 16106127360 V[30]: 1073741823
O[31]= 33285996544 V[31]: 2147483647
O[32]= 68719476736 V[32]: 4294967295
O[33]= 141733920768 V[33]: 8589934591
O[34]= 292057776128 V[34]: 17179869183
O[35]= 601295421440 V[35]: 34359738367
O[36]= 1236950581248 V[36]: 68719476735
O[37]= 2542620639232 V[37]: 137438953471
O[38]= 5222680231936 V[38]: 274877906943
O[39]= 10720238370816 V[39]: 549755813887
O[40]= 21990232555520 V[40]: 1099511627775
O[41]= 45079976738816 V[41]: 2199023255551
O[42]= 92358976733184 V[42]: 4398046511103
O[43]= 189115999977472 V[43]: 8796093022207
O[44]= 387028092977152 V[44]: 17592186044415
O[45]= 791648371998720 V[45]: 35184372088831
O[46]= 1618481116086272 V[46]: 70368744177663
O[47]= 3307330976350208 V[47]: 140737488355327
O[48]= 6755399441055744 V[48]: 281474976710655
O[49]= 13792273858822144 V[49]: 562949953421311
O[50]= 28147497671065600 V[50]: 1125899906842623
O[51]= 57420895248973824 V[51]: 2251799813685247
O[52]= 117093590311632896 V[52]: 4503599627370495
O[53]= 238690780250636288 V[53]: 9007199254740991
O[54]= 486388759756013568 V[54]: 18014398509481983
O[55]= 990791918021509120 V[55]: 36028797018963967
O[56]= 2017612633061982208 V[56]: 72057594037927935
O[57]= 4107282860161892352 V[57]: 144115188075855871
O[58]= 8358680908399640576 V[58]: 288230376151711743
O[59]= 17005592192950992896 V[59]: 576460752303423487
O[60]= 16140901064495857664 V[60]: 1152921504606846975
O[61]= 14987979559889010688 V[61]: 2305843009213693951
O[62]= 13835058055282163712 V[62]: 4611686018427387903
O[63]= 13835058055282163712 V[63]: 9223372036854775807
Enter 0 to break
12
Total Number of 1's between 0 to 12 : 22
0

Process returned 0 (0x0)   execution time : 6.186 s
Press any key to continue.