백준 9527 1의 개수 세기

두 수를 입력받아 두 수 사이의 모든 수를 2진수로 표현했을때 1의 개수를 구하는 문제이다.

일단, 문제 접근을 1 부터 어떤 숫자까지의 범위에서 1의 개수를 구하는 것으로 생각하고 시작했다.

 

MSB가 2^k일때, 그 이진수 숫자가 표현할 수 있는 모든 숫자의 1의 수를 d[k]라고 하자. (k 는 0부터 시작)

d[k]는 d[k-1] + d[k-1] + 2^k로 표현 가능하다. 첫번째 d[k - 1]는 k번째 bit 꺼져있을때 밑 자리 애들의 합이고, 두번째 d[k - 1]은 k 번째 bit가 켜져있을때 밑 자리 애들의 합이다. 그 뒤 2^k는 k번째 bit가 켜졌을 때의 개수를 합하였다.

 

이 방식으로, d[k] 배열을 만들 수 있다. 이 배열을 완성시키고 나서 1 ~ 입력한 수 까지의 1 개수를 구하는 함수를 실행시켜 답을 얻을 수 있다.

그럼 이제 우리는 MSB 기준으로 1의 개수를 셀 수 있다.

이제 일반 수 x를 기준으로 거기서 1의 개수를 어떻게 세는지 보자.

그 수를 2진수로 표현하면, 거기서도 MSB를 찾을 수 있다. 그 MSB가 j 라고 하면, 우리는 d[j - 1] 로 밑 범위에서 1의 개수를 구할 수 있다.

그리고, 현재 j번째 비트에서의 1의 개수를 셀 수 있다. (x - 2^j + 1). 여기까지 더해준 다음, x 에서 2^j를 빼고 j를 한 비트 내려준다. 

이걸 0번째 비트까지 반복하면 된다.

 

+ 0번째 비트는 짝수인지 홀수인지 판별해서 더해주기만 하면 된다.

---

#include <iostream>

long long calc1Cnt(long long x, long long d[])
{
    long long ret = 1 & x;
    for (long long i = 54; i > 0; i--)
    {
        if (x & (1LL << i))
        {
            ret += d[i - 1] + (x - (1LL << i) + 1);
            x -= (1LL << i);
        }
    }
    return ret;
}


int main()
{
    long long d[55];
    long long a, b;
    d[0] = 1;
    for (long long i = 1; i < 55; i++)
    {
        d[i] = d[i-1] * 2 + (1LL << i);
        // std::cout << d[i] << " ";
    }
    std::cin >> a >> b;

    std::cout << calc1Cnt(b, d) - calc1Cnt(a - 1, d);
}

처음 접근은 맨땅에 헤딩하기었는데, 루프돌면서 각 비트 마스킹해서 참이면 한개씩 올려줬다. 좀 개수 써보면서 접근할걸...

주말동안 진짜 정신없었다. 이제 마음챙기면서 장기전을 준비해야겠다.

 

오늘도 평온한 하루가 되길. 슨민.