# 1404. Number of Steps to Reduce a Number in Binary Representation to One
###### tags: `Leetcode` `Medium` `Bit Manipulation`
Link: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/description/
## 思路
从后往前遍历
1. 当我们没有遇到1的时候 正常加一个operation即可
2. 当遇上第一个1 我们加两个operation 并且把carry设成1
3. 遇上第一个1之后 如果我们又遇到1 carry会把它变成0 所以只需要一个operation carry依然是1; 如果遇到的是0 carry会把它变成1 所以需要两个operation carry还是1

所以遇到第一个1之后carry永远是1
## Code

class Solution {
    public int numSteps(String s) {
        int res = 0, carry = 0;
        for(int i=s.length()-1; i>0; i--){
            res++;
            if(s.charAt(i)-'0'+carry==1){
                carry = 1;
                res++;
            }
        }
        return carry+res;
    }
}