The C++ Program: bitcounting.cpp

  1 /*
  2  * Sample solution for Bit Counting
  3  *    Steven J Zeil, 10/21/2010
  4  */
  5 #include <iostream>
  6 #include <algorithm>
  7 
  8 
  9 using namespace std;
 10 
 11 int kSteps[64];  // kSteps[i] number of steps to converge to 1 starting with i
 12 
 13 
 14 long long unsigned bitDistribution[64][64];
 15 // bitDistribution[i][j] = # of numbers in the range 0..2^i-1 that 
 16 //    have j one bits in their representation
 17 //   The pattern is familiar:
 18 //     1
 19 //     1 1
 20 //     1 2 1
 21 //     1 3 3 1
 22 // etc.
 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       //cerr << "m " << m << "\tpower " << power << endl;
 80       if (m % 2LLU == 1LLU)
 81         {
 82           --numOnesSoFar;
 83           //cerr << "checking 0..2^" << power << endl;
 84           // 2^power has one one-bit (plus however many bits appear to the left)
 85           ++(distribution[1+numOnesSoFar]);
 86           // Add in the number of ints from 0..2^power-1
 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   // Sanity check
106   long long unsigned count2 = 0;
107   for (int i = 0; i < 64; ++i)
108     count2 += numbersByBitCount[i];
109   if (count2 != m+1LLU)
110     cerr << "**Inconsistency detected for m =" << m << ": " << count2 << endl;
111 
112   cerr << "In the range 0.." << m << " the numbers are distributed as\n";
113   for (int i = 0; i < 16; ++i)
114     cerr << numbersByBitCount[i] << ' ';
115     cerr << endl;
116   */
117   for (int bits = 0; bits < 64; ++bits)
118     if (kSteps[bits] + 1 == desiredK)
119       count += numbersByBitCount[bits];
120 
121   // Special case: K(1) == 0, but the above caculation treats it as 1
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       //cout << lo << " "  << hi << " " << k << endl;
154       if (lo == 0L)
155         break;
156       bitcounting (lo, hi, k);
157     }
158   return 0;
159 }