[Gold II] 1의 개수 세기 - 9527

문제 링크

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

문제 설명

두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.

즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.

 $$\sum _{x=A}^{B}f(x)$$ 

입력

첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10¹⁶)

출력

1의 개수를 세어 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

long long a, b;

// dp[i] = 1부터 2^(i-1) 까지 이진수에서 1의 개수 누적합
// dp[0] = 1: 1 (1개의 "1")
// dp[1] = 4: 1, 2, 3 (4개의 "1")
// dp[2] = 12: 1 ~ 7 (12개의 "1")
// dp[3] = 32: 1 ~ 15 (32개의 "1")
vector<long long> dp = { 1 };

long long solution(long long x) {
	if (x <= 2) return x;

	long long k = 2;          // 현재 자리값 (2^1 = 2부터 시작)
	int highest_bit = 0;      // 가장 높은 비트 위치

	// x가 현재 자리(k * 2)를 넘지 않을 때까지 비트 이동
	// k: 현재 자리값, highest_bit: 가장 높은 비트 위치
	while (k * 2 <= x) {
		k <<= 1; // k *= 2
		highest_bit++;
	}

	// 계산:
	// 1. dp[k]: 2^(k-1)까지 누적합
	// 2. (x - k + 1): 현재 자리에서 "1"의 개수 (2^highest_bit ~ x)
	// 3. solution(x - k): 나머지 숫자(x - 2^highest_bit)에 대해 재귀 호출

	// 예시: solution(10) 호출
	// k = 8 (2^3), highest_bit = 3
	// return = dp[3] + (10 - 8 + 1) + solution(10 - 8) = 12 + 3 + solution(2) = 17
	return dp[highest_bit] + x - k + 1 + solution(x - k);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	long long current_power = 1; // 현재 자리값 (2^0 = 1)

	// dp[k+1] = (dp[k] + 2^k) * 2
	// 각 자리에서:
	// - 이전 자리 누적합(dp[k])
	// - 현재 자리의 "1" 개수 추가(2^k)
	// - 다음 자리로 확장(곱하기 2)
	for (int k = 0; k < 60; k++) { // 최대 2^59까지 계산
		dp.push_back((dp.back() + current_power) * 2);
		current_power <<= 1; // current_power *= 2
	}

	cin >> a >> b;

	// [a, b] 구간의 "1"의 개수 합
	// solution(b): 1부터 b까지 "1"의 개수
	// solution(a - 1): 1부터 a-1까지 "1"의 개수
	cout << solution(b) - solution(a - 1);

	return 0;
}