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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net



일단 자연수 N에 대해서 1부터 N까지 이진수에 1 개수 합 구하는 함수 func 만들고


func(B) - func(A-1) 구하는 방식으로 했음



함수 func는 자연수 N에 대해서 l = (int)log2(N) 구해주고, 


1부터 2^l-1까지 1 개수, 2^l자리 1 개수 더한 다음


1의 자리부터 2^(l-1) 자리까지 1 개수는 0부터 (N - 2^l)까지랑 2^l 부터 N까지 같으니까

재귀함수로 N - 2^l 넣어서 1 개수 계산하고


이렇게 했는데 왜 계속 틀리냐........



구글링 좀  했는데 나랑 같은 아이디어 쓴 코드 있어서 비교해봤는데 그래도 왜 틀렸는지 모르겠음


아래는 소스코드


#include <iostream>

#include <cmath>


using namespace std;


typedef long long int llint;


llint calc(llint A)

{

if(A <= 1){

return A;

}

llint ret=0;

llint r1, r2, r3;

int l;

// l: (int)log2(A), 

for(int i = 1; i < 64; i++){

if(pow(2, i) <= A && A < pow(2, i+1)){

l = i;

break;

}

}

// 1부터 2^n - 1 까지 1의 개수:  n * 2^(n-1)

r1 = (llint)l * pow(2, l-1);

// 2^l 이상 A 이하 수를 이진수로 표현할 때,  2^l의 자리 1의 수 

r2 = A - (pow(2, l) - 1);

// 재귀함수를 통한 계산

r3 = calc(A - pow(2, l));

ret += r1+r2+r3;

return ret;

}


int main(void)

{

llint A, B;

cin >> A >> B;

cout << calc(B) - calc(A-1) << endl;

return 0;

}