[9527] 1의 개수 세기

문제

https://www.acmicpc.net/problem/9527

입력

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

출력

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

풀이

풀지 못해서 다른 사람의 풀이를 해석 해보았습니다.

2의 n제곱인 값의 1의 개수는 1입니다. ex) 2 = 10, 4 = 100, 16 = 10000

그렇다면 2의 n제곱까지 누적된 1의 개수는 (2의 n제곱 - 1)의 누적된 1의 개수 더하기 1이 됩니다.

여기서 (2의 n제곱 - 1)까지 누적된 1의 개수는 규칙성이 존재합니다. 만약 해당 값이 7이라 가정하면

001
010
011
100
101
110
111

이러한 값의 1의 개수를 계산하면 되는데 자릿수마다 동일한 개수가 나온다는 것을 알 수 있습니다.

이를 수식으로 표현하면 자릿수마다 1이 2^n / 2개가 존재하고, 따라서 총 1의 개수는 n * (2^n/2) 이라 표현할 수 있습니다. 코드로 작성하면 다음과 같습니다.

def get_count(num):
    if num <= 0:
        return 0
    n = int(math.log2(num))
    left = 2 ** n
    if left == num: # 누적된 1의 개수를 구하려는 숫자가 2^n에 해당하는 수일 때 
        return (n * left // 2) + 1

다음으로 2^n, 2^n-1 에 해당하지 않는 값의 개수를 구하는 방법을 알아야합니다.

해당 값을 x라 했을 때 x보다 작은 수 중에 가장 큰 2^n의 값을 구해줍니다. 2^n의 누적된 1의 개수는 위의 방법으로 구해줄 수 있겠죠? 그럼 사실 상 2^n ≤ x 범위에 존재하는 1의 개수만 구해주면 됩니다.

2^n ≤ x 범위에 존재하는 1의 개수는 0 ≤ x-(2^n) 범위에 존재하는 1의 개수와 비슷하다는 것을 알 수 있습니다. 다만 가장 왼쪽에 1이 존재하다는 것만 제외하면 말이죠 따라서 0 ≤ x-(2^n) 범위의 1의 개수에서 각각 1을 한 번 더 더해주면 구해줄 수 있습니다. 이를 코드로 작성하면 다음과 같습니다.

def get_count(num):
    if num <= 0:
        return 0
    n = int(math.log2(num))
    left = 2 ** n
    if left == num:
        return n * left // 2 + 1
    interval = num - left
    return get_count(left) + interval + get_count(interval)

정답 코드

import sys
import math

sys.setrecursionlimit(10 ** 8)
A, B = map(int, sys.stdin.readline().split())

def get_count(num):
    if num <= 0:
        return 0
    n = int(math.log2(num))
    left = 2 ** n
    if left == num:
        return n * left // 2 + 1
    interval = num - left
    return get_count(left) + interval + get_count(interval)

print(get_count(B) - get_count(A-1))