Given a number s in their binary representation. 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’s guaranteed that you can always reach to one for all testcases.

    Example 1:

    1. Input: s = "1101"
    2. Output: 6
    3. Explanation: "1101" corressponds to number 13 in their decimal representation.
    4. Step 1) 13 is odd, add 1 and obtain 14. 
    5. Step 2) 14 is even, divide by 2 and obtain 7.
    6. Step 3) 7 is odd, add 1 and obtain 8.
    7. Step 4) 8 is even, divide by 2 and obtain 4.  
    8. Step 5) 4 is even, divide by 2 and obtain 2. 
    9. Step 6) 2 is even, divide by 2 and obtain 1.

    Example 2:

    1. Input: s = "10"
    2. Output: 1
    3. Explanation: "10" corressponds to number 2 in their decimal representation.
    4. Step 1) 2 is even, divide by 2 and obtain 1.

    Example 3:

    1. Input: s = "1"
    2. Output: 0

    Constraints:

    • 1 <= s.length <= 500
    • s consists of characters ‘0’ or ‘1’
    • s[0] == '1'

    题意

    对于一个二进制表示的数，如果它是偶数，则将其除以2；如果它是奇数，则加上1。统计将这个二进制数变为1所需要的操作次数。

    思路

    因为二进制长度最大为500，不能转化为十进制整数再进行处理。直接对字符串按照操作步骤进行处理: 如果当前二进制末位为0，则右移一位；如果末位为1，则加1。

    代码实现

    1. class Solution {
    2.     public int numSteps(String s) {
    3.         char[] bits = s.toCharArray();
    4.         int carry = 0;
    5.         int tail = bits.length - 1;
    6.         int count = 0;
    8.         // 处理到只剩下一位
    9.         while (tail > 0) {
    10.             if (bits[tail] == '1' && carry == 1) {
    11.                 carry = 1;
    12.                 count += 1;
    13.             } else if (bits[tail] == '0' && carry == 0) {
    14.                 carry = 0;
    15.                 count += 1;
    16.             } else {
    17.                 carry = 1;
    18.                 count += 2;        // 加2是进行了两步操作：先对二进制加1使其末位为0，再右移一位
    19.             }
    20.             tail--;
    21.         }
    23.         // 原二进制数中的第一位必为'1'，如果还存在进位，则需要再进行一次右移操作
    24.         return carry == 1 ? count + 1 : count;
    25.     }
    26. }