백준 9527번 1의 개수 세기 문제풀이

입력

두 자연수 A, B (1 ≤ 10^16)

입력범위가 굉장히 넓다.

전체적인 범위에서 어떤 수를 이진수로 바꾸고 그 차이에 대해서

바깥의 1을 컨테이너라고 지정하고 그게 그 모든 경우의수가

쉽게말해서 16부터 31 사이의 수라면

바깥 1은 15번 등장하고 나머지는 모든 경우의 수의 절반 말그대로 888 등장할것임

출력

어떤 두 수 사이의 수들에 대해서 1이 등장하는 횟수를 출력해라.

과정

입력값이 10 ^ 16까지기 때문에 모든 수를 늘려가면서 세는것은 엄두도 못 낼 일 

 

다만 직관적으로 이해하기 쉬운건 1이 등장하는데 패턴이 있을 것이라는 점이다.

예를들어 0000(2)부터 1111(2)까지 1이 등장하는 횟수는 당연히 32회다.중복 순열의 총 경우의수에 각각의 자리수가 등장할 확률은 1/2를 곱하면 되기 때문이다.

그렇다면 00000부터 10000(2)까지 역시 쉽게 33회라는 걸 알 수 있다. 1111(2)에서 1를 더해서 추가해주면 되니까. 이런 패턴이 다른 숫자인 1000000(2) 등에 대해서도 같이 반복될 것이란걸 알 수 있다. 

10000(2)역시 각 자리수에 대해서 따져보면

• 가장 왼쪽의 자리수는 1번 등장 [ 10000 ]
• 2번째 자리수는 8번 등장
• 3번째 자리수는 8번 등장
• 4번째 자리수 8번 등장
• 마지막 자리수 8번 등장

일단 여기서 모든 자리수가 자기 왼쪽에 숫자가 있으면 그 숫자의 반만큼 등장한다는걸 알 수 있다. 조금 더 발전시켜 10010(2) 를 확인해보자

• 가장 왼쪽의 자리수는 3번 등장 [ 10000 ] [ 10001] [10010] 
• 2번째 자리수는 8번 등장
• 3번째 자리수는 8번 등장
• 4번째 자리수 9번 등장 [ 10000 까지 8개 + 10010 ]
• 마지막 자리수 9번 등장 [ 10000 까지 8개 + 10001 ]

추가적인 가정이 생겼다 모든 자리수의 1은 자기 오른쪽에 있는 놈들만큼 등장하며 또한 자기 자리수가 현재 1일경우 1이 추가된다는 것

이 가정을 일반화 시켜보면

10101이다 ⇒ 10000부터 여기까진 ⇒ [101번등장] [0번등장] [2번등장] [4번등장][]

1부터 여기까진 ⇒ [101번 등장] [10000 / 2번 등장] [10000 / 2 번 등장 + 01번 + 1번등장] [10100/2 번등장 ] + [10100 / 2 번 등장 + 1 번등장 ?]

한마디로 자기 왼쪽에 값들의 절반만큼 자기가 등장하고 자기가 1일경우는 자기 오른쪽에 있는 애들만큼 등장한다고 할 수 있다.

 

결과물

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

long long countTotal1(long long inp)
{

    long long forLeft = 0;
    long long forRight = inp;
    long long ans = 0;
    int GreatIndex = 0;
    long long GreatVal = 1;
    while (inp >= GreatVal)
    {
        GreatIndex++;
        GreatVal *= 2;
    }
    GreatIndex--;
    GreatVal /= 2;
    while (GreatIndex >= 0)
    {
        ans += (forLeft / 2);

        if (inp & GreatVal)
        {
            forRight -= GreatVal;
            ans += forRight + 1;
            forLeft |= GreatVal;
        }
        GreatVal /= 2;
        GreatIndex--;
    }

    return ans;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);

    long long A, B;
    cin >> A >> B;

    int C = 0;
    int index = 0;

    cout << countTotal1(B) - countTotal1(A - 1) << '\n';

}