Find Rightmost unset bit of a very large number

Question

How to obtain rightmost unset bit position of a number N in c++.

1<= N <= 2^60

storing as number does not work since 2^60 can only be stored in string. thus following does not work

long long getBitUtil(long long n) { 
    return log2(n&-n)+1; 
} 

long long getBit(long long n) { 
    return getBitUtil(~n);         
} 

Answer 1

Try this. Code is self explanatory with comments

int getRightmostUnSetBit(string s, int pos)
{
    int l= s.size();
    int lc = s[l-1];
    if(lc>=48 && lc<=57 && lc%2 ==0)
        return pos; // if last digit is even return position
    else
    {// divide the number into half and call function again.
        string s2 = "";
        int rem =0;
        for(int i =0; i<l;i++)
        {
            int d = s[i]-'0';
            d = rem *10 + d;
            int q = d/2;
            rem = d%2;
            s2.push_back('0'+q);
        }
        return getRightmostUnSetBit(s2,pos+1); //call for s2
    }
}

Take input in string and call from main

int pos = getRightmostUnSetBit(s,1);// will not work if s is "0" or similar to "000...". So check for it before function calling.