Palindromic Binary Representation

• Time : O(logA)
• Space : O(1)

int Solution::solve(int A) {
    if(A == 1) return 1;
    int p = 1, bit = 0;
    A -= 2;
    while(A > 3*p) {
        A -= 3*p;
        p *= 2;
    }
    if(A > p) {
        A -= p;
        p += (A/2);
        if(A & 1) bit = 2;
        else bit = 1;
    } else p += A;
    
    string pal = "";
    while(p) {
        if(p & 1) pal.push_back('1');
        else pal.push_back('0');
        p>>=1;
    }
    string rev = pal;
    reverse(begin(rev),end(rev));
    pal = rev + (bit == 0 ? "" : bit == 1 ? "0" : "1") + pal;
    
    int res = 0;
    p = 0;
    while(pal.size()) {
        if(pal.back() == '1') res |= 1<<p;
        pal.pop_back();
        p++;
    }
    return res;
}