PKU 3252 Round Numbers

• うまい解法が思いつかなかったためテーブル埋込みを使いました
• 2^20個を1セットとしてテーブルに持たせ、端数の部分を全探索しました

int numofbits5(ulong bits) {
  bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
  bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
  bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
  bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
  return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}
int nlz(ulong  x) {
  x = x | ( x >>  1 );
  x = x | ( x >>  2 );
  x = x | ( x >>  4 );
  x = x | ( x >>  8 );
  x = x | ( x >> 16 );
  return numofbits5(x);
}

bool isRound(ulong value)
{
		const int pop = numofbits5(value);
		const int size = nlz(value);
		return pop * 2 <= size;
}

int main()
{
	ulong start, finish;
	cin >> start >> finish;

	int counter = 0;
	if ((start >> 20) == (finish >> 20)) {
		for (int i = start; i <= finish; ++i) {
			if (isRound(i)) {
				++counter;
			}
		}
	} else {
		for (int i = start; i < (((start >> 20) + 1) << 20); ++i) {
			if (isRound(i)) {
				++counter;
			}
		}
		for (int i = ((finish >> 20) << 20); i <= finish; ++i) {
			if (isRound(i)) {
				++counter;
			}
		}
		for (int up = (start >> 20) + 1; up < (finish >> 20); ++up) {
			counter += table[up];
		}
	}
	cout << counter << endl;
}

//
//int main()
//{
//	vector<int> answer;
//	for (ulong up = 0; up < (1 << 11); ++up) {
//		int counter = 0;
//		for (ulong down = 0; down < (1 << 20); ++down) {
//			const ulong value = (up << 20) | down;
//			const int pop = numofbits5(value);
//			const int size = nlz(value);
//			if (pop * 2 <= size) {
//				++counter;
//			}
//		}
//		answer.push_back(counter);
//		cout << counter << "," << endl;
//	}
//}