백준_9527_1의 개수 세기

문제

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

9527번: 1의 개수 세기

풀이

1) 패턴 파악하기

1의 자리수는 (0, 1)이 반복된다. (0이 1개, 1이 1개)

2의 자리수는 (0, 0, 1, 1)이 반복된다. (0이 2개, 1이 2개)

4의 자리수는 (0, 0, 0, 0, 1, 1, 1, 1)이 반복된다. (0이 4개, 1이 4개)

...

2**n의 자리수는 (0...., 1....)이 반복된다. (0이 2**n개, 1이 2**n개)

 

그룹의 절반은 0, 나머지 절반은 1로 채워져 있다.

2) 0부터 10까지 1의 개수

1의 자리	(0, 1)	그룹이 5개	나머지 1개
2의 자리	(0, 0, 1, 1)	그룹이 2개	나머지 3개
8의 자리	(0, 0, 0, 0, 1, 1, 1, 1)	그룹이 1개	나머지 3개
16의 자리	(0, 0, 0, 0, 0, 0, 0, 0,  1, 1, 1, 1, 1, 1, 1, 1)	그룹이 0개	나머지 10개

코드

def getCount(n) : 
    n+=1
    size = len(bin(n))-2
    ans = 0
    
    for i in range(size) : 
        group = 2**(i+1)
        subGroup = 2**i # 그룹의 절반
        div, mod = divmod(n, group) # 그룹의 수, 나머지
        
        ans += (n-mod)//2
        if subGroup < mod : # 나머지가 그룹의 절반이 넘어가면,
            ans += mod-subGroup
    
    return ans

a, b = map(int, input().split())
print(getCount(b)-getCount(a-1))