1404. Number of Steps to Reduce a Number in Binary Representation to One

Given the binary representation of an integer as a string s, return the number of steps to reduce it to 1 under the following rules:

• If the current number is even, you have to divide it by 2.
• If the current number is odd, you have to add 1 to it.

It is guaranteed that you can always reach one for all test cases.

class Solution {
public:
    int numSteps(string s) {
        int res = 0;
        while(s.length() > 1) {
            if(s.back() == '0') s.pop_back();
            else {
                int carry = 1, n = s.length();
                s.back() = '0';
                for(int i = n - 2; i >= 0 and carry; i--) {
                    if(s[i] == '1') s[i] = '0';
                    else {
                        s[i] = '1';
                        carry = 0;
                    }
                }
                if(carry) s = '1' + s;
            }
            res++;
        }
        return res;
    }
};