[백준 9527] 1의 개수 세기 [C]

백준 - 9527

---

풀이

16까지 1의 분포는 다음과 같다.

N	N의 2진수	1의 개수
1	1	1
2	1 0	2
3	1 1	4
4	1 0 0	5
5	1 0 1	7
6	1 1 0	9
7	1 1 1	12
8	1 0 0 0	13
9	1 0 0 1	15
10	1 0 1 0	17
11	1 0 1 1	20
12	1 1 0 0	22
13	1 1 0 1	25
14	1 1 1 0	28
15	1 1 1 1	32
16	1 0 0 0 0	33

 

2^x 자리 수는 2^(x+1)마다 반복된다는 것을 알 수 있다.

때문에, (N+1)을 2^(x+1)로 나눈 몫을 2^x만큼 곱하면 완전히 반복되는 구간에 존재하는 1의 개수를 구할 수 있다.

완전히 반복되지 않은 구간에서의 1의 개수는,  2^x 자리 수가 1인경우 (N+1)을 2^x로 나눈 나머지의 개수이다.

---

소스코드

#include <stdio.h>
#define ll long long
ll count(ll n){
    ll cnt = 0, a = n, b = 1;
    while (a){
        cnt += (n+1)/(b << 1) *b;
        if (a & 1) cnt += (n+1)%b; 
        a >>= 1;
        b <<= 1;
    }
    return cnt;
}
int main(){
    long long A, B;
    scanf("%lld %lld", &A, &B);
    printf("%lld", count(B) - count(A-1));
}

---

출처

9527번: 1의 개수 세기