The C++ Program: bitcounting.cpp
1
2
3
4
5 #include <iostream>
6 #include <algorithm>
7
8
9 using namespace std;
10
11 int kSteps[64];
12
13
14 long long unsigned bitDistribution[64][64];
15
16
17
18
19
20
21
22
23
24
25
26 unsigned numOnesIn (unsigned long long m)
27 {
28 unsigned cnt = 0;
29 while (m > 0) {
30 if (m % 2LLU == 1LLU)
31 ++cnt;
32 m = m / 2LLU;
33 }
34 return cnt;
35 }
36
37 unsigned basicStepCount (unsigned int m)
38 {
39 unsigned k = 0;
40 if (m > 1LLU)
41 {
42 unsigned n = numOnesIn(m);
43 ++k;
44 while (n > 1) {
45 n = numOnesIn(n);
46 ++k;
47 }
48 return k;
49 }
50 else
51 return 1;
52 }
53
54 void setup()
55 {
56 kSteps[0] = kSteps[1] = 0;
57 for (unsigned int i = 2; i < 64; ++i)
58 kSteps[i] = basicStepCount(i);
59 for (int j = 0; j < 64; ++j)
60 bitDistribution[0][j] = 0;
61 bitDistribution[0][0] = 1;
62 for (int i = 1; i < 64; ++i)
63 {
64 bitDistribution[i][0] = 1;
65 for (int j = 1; j < 64; ++j)
66 bitDistribution[i][j] = bitDistribution[i-1][j-1] + bitDistribution[i-1][j];
67 }
68 }
69
70
71 unsigned distributeNumberByBits (unsigned long long m, unsigned long long* distribution)
72 {
73 int power = 0;
74 int numOnesSoFar = numOnesIn(m);
75 fill_n (distribution, 64, 0LLU);
76 distribution[0] = 1;
77 while (m > 0LLU)
78 {
79
80 if (m % 2LLU == 1LLU)
81 {
82 --numOnesSoFar;
83
84
85 ++(distribution[1+numOnesSoFar]);
86
87 for (int bits = 1; bits <= power+1; ++bits)
88 {
89 unsigned long long numNumbers = bitDistribution[power][bits];
90 distribution[bits+numOnesSoFar] += numNumbers;
91 }
92 }
93 ++power;
94 m = m / 2LLU;
95 }
96 }
97
98
99 unsigned long long stepCountInRange (unsigned long long m, unsigned desiredK)
100 {
101 unsigned long long count = 0LLU;
102 unsigned long long numbersByBitCount[64];
103 distributeNumberByBits (m, numbersByBitCount);
104
105
106
107
108
109
110
111
112
113
114
115
116
117 for (int bits = 0; bits < 64; ++bits)
118 if (kSteps[bits] + 1 == desiredK)
119 count += numbersByBitCount[bits];
120
121
122 if (m >= 1UL)
123 {
124 if (desiredK == 0)
125 ++count;
126 else if (desiredK == 1)
127 --count;
128 }
129
130 return count;
131 }
132
133
134 void bitcounting (unsigned long long lo, unsigned long long hi, unsigned k)
135 {
136 unsigned long long cnt1 = stepCountInRange(lo-1LLU, k);
137 unsigned long long cnt2 = stepCountInRange(hi, k);
138 cout << cnt2-cnt1 << endl;
139 }
140
141
142
143
144
145 int main (int argc, char** argv)
146 {
147 setup();
148 while (cin)
149 {
150 unsigned long long lo, hi;
151 unsigned k;
152 cin >> lo >> hi >> k;
153
154 if (lo == 0L)
155 break;
156 bitcounting (lo, hi, k);
157 }
158 return 0;
159 }