[python] 백준 9526 1의 개수 세기

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

9527번: 1의 개수 세기

 

문제해결

• 비트마스크 문제라는 것을 바로 알 수 있었다. (이진법을 이용한 1과 0을 이용해서 1의 개수를 세는 것이므로)
• 이진법에는 패턴이 있다. 0000-> 0001 ->0010->0011 ... (1의 자리수 01010101/ 2의 자리수 00110011 ....)
• 그 패턴을 써보고 풀어보면 바로 풀 수 있는 문제

 

CODE

import math

a, b = map(int, input().split())

def solve(x):
    if x<=0:
        return 0
    l = int(math.log2(x))
    num = 2**l
    if num == x:
        return l*x//2+1 # +1은 마지막 1개 10000(2) 같은거. 참고로 0~x-1보고 x 1개 보는 경우임
    diff = x - num
    return solve(num) + diff+solve(diff) #diff는 앞자리 1을 diff만큼 더한다는 뜻
print(solve(b)-solve(a-1))