[백준 C++] 9527번 1의 개수 세기

9527번: 1의 개수 세기

문제 요약

문제

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

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

사용 알고리즘

수학, 누적합

입출력

• 입력: 첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 1016)
• 출력: 1의 개수를 세어 출력한다. ``` 예제1

입력 2 12 출력 21

## 풀이
누적합으로 풀어야 한다. N이 주어졌을때 0부터 N까지의 1의 개수를 바로 세어야 한다. N을 이진수로 바꾼 뒤 각 자리에서 1이 나오는 경우를 보면 규칙적으로 나오는 것을 알 수 있다. 그 규칙에 따라서 자리수를 하나씩 올리면서 1의 개수를 세면 된다.

## 어려웠던 점
숫자가 매우 크게 나오므로 long long을 했어야 했다. 일반 정수를 long long으로 취급되게 하려면 ll을 붙여야 하는데 안붙여서 오류났었다. 처음에는 일반적인 for문을 사용하여 계산식에 시프트 연산자로 계산했는데 시간초과 나서 for문에 바로 시프트연산자를 쓰니 통과했다.

## 배운 점 / 느낀 점
시프트 연산자도 많이 사용하면 오래걸린다. 2의 제곱수는 항상 시프트 연산자를 먼저 생각하자.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long a, b;

long long countone(long long n){
    long long s = 0;
    for (long long i = 1; i <= n; i<<=1) {
        s += (n+1)/(i<<1)*i;
        s += max((n+1) % (i<<1)-i, 0ll);
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> a >> b;

    cout << countone(b)-countone(a-1);
    return 0;
}