# [Gold II] 1의 개수 세기 [문제 링크](https://www.acmicpc.net/problem/9527) ## 문제 설명 <p>두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.</p> <p>즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.</p> <p>\[\sum_{x=A}^{B}{f(x)}\]</p> ## 입력 <p>첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10¹⁶)</p> ## 출력 <p>1의 개수를 세어 출력한다.</p> ## 풀이 #### 규칙은 아래와 같이 $2^0$개, $2^1$개, $2^2$개, ... 가 규칙에 따라 배치된다. #### 앞의 절반에는 이전 패턴에 0을 붙인 패턴(1의 개수 같음), 뒤의 절반에는 이전 패턴에 1을 붙인 패턴(1의 개수가 1개 큼)으로 배치된다. | 이진수 | 1의 개수 | |:---:|:----:| |1|1| |/|/| |10|1| |11|2| |/|/| |100|1| |101|2| |110|2| |111|3| #### getCnt(n) 함수를 이진수로 표현했을 때 n까지의 1의 개수라고 할 때 getCnt(B) - getCnt(A-1)를 구하면 된다. #### getCnt()는 완전히 반복되는 패턴에서 생기는 1의 개수 + 끝에 남는 부분에서 추가로 생기는 1의 개수로 수의 개수로 구현하였다. ``` c++ #include<bits/stdc++.h> using namespace std; long long getCnt(long long n) { long long ret=0, size=1, cur=1; while(size<=n) { n -= size; ret += cur; cur = cur*2 + size; size<<=1; } while(n) { if(size<=n) { n -= size; ret += cur; cur += size; } size>>=1; cur = cur-size >> 1; } return ret; } int main() { ios::sync_with_stdio(0); cin.tie(0); long long a, b; cin >> a >> b; cout << getCnt(b) - getCnt(a-1); } ```