class Solution {
public:
    string intToBinary(int n)
    {
        string str = "";
        while(n != 0){
            int digit = n%2;
            str += (char)(digit+'0');
            n = n/2;
        }
        reverse(str.begin(), str.end());
        return str;
    }
    int countDigitOne(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;

        int pow2[25];
        pow2[0] = 1;
        for(int i=1; i<25; i++) pow2[i] = pow2[i-1] * 2;

        int cntAllOne[25];
        cntAllOne[0] = 1;
        for(int i=1; i<25; i++) cntAllOne[i] = pow2[i-1] * i;

        string str = intToBinary(n);
        int len = (int) str.length();
        int answer = 0;

        int cumOneCount = 0;
        for(int i=0; i<str.length(); i++){
            if(str[i] == '0') continue;

            int suffixLength = (int) str.length()-i-1;
            int countOfNumber = pow2[suffixLength];
            answer += cumOneCount*countOfNumber;

            answer += cntAllOne[suffixLength];
            if(i != len-1) cumOneCount++;
        }
        answer += cumOneCount;
        return answer;
    }
};