---

1404. 将二进制表示减到 1 的步骤数

• 标签：位运算、字符串
• 难度：中等

题目链接

• 1404. 将二进制表示减到 1 的步骤数 - 力扣

题目大意

描述：给定一个以二进制形式表示的字符串 $s$。

要求：返回将其按照以下规则变为 $1$ 所需的步骤数：

• 如果当前数是偶数，除以 $2$。
• 如果当前数是奇数，加上 $1$。

说明：

• $1 \le s.length \le 500$。

示例：

• 示例 1：

输入：s = "1101"
输出：6
解释："1101" 表示十进制数 13 。
Step 1) 13 是奇数，加 1 得到 14 
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7  是奇数，加 1 得到 8
Step 4) 8  是偶数，除 2 得到 4  
Step 5) 4  是偶数，除 2 得到 2 
Step 6) 2  是偶数，除 2 得到 1

• 示例 2：

输入：s = "10"
输出：1
解释："10" 表示十进制数 2 。
Step 1) 2 是偶数，除 2 得到 1

解题思路

思路 1：模拟二进制运算

1. 核心思想

直接模拟二进制运算。从右往左（最低位到最高位）处理。

• 如果末尾是 '0'（偶数）→ 除以 $2$（右移一位），步数 $+1$。
• 如果末尾是 '1'（奇数）→ 加 $1$（引起进位），步数 $+1$。

关键：加 $1$ 操作可能引起连续进位，需要处理。

2. 具体步骤

第 1 步：将 $s$ 转为列表方便修改。

第 2 步：从末尾向前遍历：

• 如果当前位是 '1'：加 $1$（进位），步数 $+1$。
  • 进位：从当前位置向左找到第一个 '0'，将其变为 '1'，中间的 '1' 全变 '0'。
  • 如果全是 '1'，说明需要扩展位数（前面加一个 '1'）。
• 如果当前位是 '0'：除 $2$（相当于移出末尾），步数 $+1$。

第 3 步：当只剩下 $1$ 时停止。最后一位 '1' 不需要额外步骤。

优化：不需要真的修改字符串，只需要从右向左模拟，维护进位状态。

3. 举例说明

以 $s = "1101"$ 为例：

步骤	当前数	操作	结果
1	1101	奇数(+1)→1110	1 步
2	1110	偶数(/2)→111	1 步
3	111	奇数(+1)→1000	1 步
4	1000	偶数(/2)→100	1 步
5	100	偶数(/2)→10	1 步
6	10	偶数(/2)→1	1 步

共 $6$ 步。

思路 1：代码

class Solution:
    def numSteps(self, s: str) -> int:
        steps = 0
        carry = 0  # 进位标记
        # 从最低位到最高位（除去最高位）
        for i in range(len(s) - 1, 0, -1):
            bit = (int(s[i]) + carry) % 2
            if bit == 1:
                # 奇数：加 1
                steps += 2  # 加 1 操作 + 后续除 2
                carry = 1
            else:
                # 偶数：除 2
                steps += 1
        # 处理最高位
        # 如果最高位有进位（即原来的数 + carry）
        if carry == 1:
            # 最高位 0+1=1（无需处理）或 1+1=10（还需要一次除 2）
            first_bit = int(s[0]) + carry
            if first_bit == 2:
                # 剩余为 "10"，除 2 一次
                steps += 1
        return steps

更简洁的版本（模拟过程中检查长度）：

class Solution:
    def numSteps(self, s: str) -> int:
        steps = 0
        carry = 0
        n = len(s)
        for i in range(n - 1, 0, -1):
            if (int(s[i]) + carry) % 2 == 0:
                steps += 1
            else:
                steps += 2
                carry = 1
        # 最高位
        if carry:
            # 如果最高位原本是 1，加上进位变成 10，需要额外一步除 2
            if s[0] == '1':
                steps += 1
        return steps

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。