One 、 subject

1、 Title Description

   Give you an integer $n$, You need to repeat the following several times to convert it to $0$ ：
    1） Flip $n$ The rightmost bit in the binary representation of （ The first $0$ position ）.
    2） If the first $(i-1)$ Position as $1$ And from the $(i-2)$ Position to the first $0$ All for $0$, Then flip $n$ In the binary representation of $i$ position .
   Return to $n$ Convert to $0$ Minimum number of operations .
   The sample input ： n = 3
   Sample output ： 2

2、 Basic framework

• C Language The basic framework code given in version is as follows ：

int minimumOneBitOperations(int n){
    

}

3、 Original link

LeetCode 1611. Change an integer to 0 The minimum number of operations

Two 、 Problem solving report

1、 Thought analysis

  $(1)$ $1$ adopt $1$ Time become $0$;
  $(2)$ $10$ By first becoming $11$, Then flip the highest position to $01$, And then it becomes $0$, in total 3 Time ;
  $(3)$ $100$ adopt 3 The next change is $110$, Then flip the highest position to $010$, Become... Again and again $0$, in total 7 Time ;
  $(4)$ According to mathematical induction , We found that , about $1\underset{k}{\underbrace{0...0}}$, Change to $0$ Times of $2^{k+1}-1$ Time ;
  $(5)$ Then we compare a number $n$ Binary decomposition $n=(101011{)}_2$ , Then we must first find a way to put the highest $1$ become $0$, So it turns into seeking general $(01011{)}_2$ Turn into $(10000{)}_2$ The minimum number of steps ; And for $(01011{)}_2$ To translate into $(10000{)}_2$, It can be transformed into $(1011{)}_2$ Turn it into $(1000{)}_2$ The minimum number of steps ; Then is $(011{)}_2$ To become $(000{)}_2$, That is to say $(11{)}_2$ become $(00{)}_2$;
  $(6)$ So we get the algorithm ：
    $(6.1)$ First of all, will $n$ Binary decomposition ;
    $(6.2)$ If you want to change a number to $1\underset{k}{\underbrace{0...0}}$ , Call recursion dfs1(n); If you want to change to $0$, Call recursion dfs2(n), So recursively solve dfs2(n) That's the answer .

2、 Time complexity

   Worst time complexity $O(lo{g}_{2}n)$ .

3、 Code details

int dfs1(int *bit, int d);            // (1)
int dfs2(int *bit, int d);            // (2)

int dfs1(int *bit, int d) {
               
    if(d == 0) {
    
        return bit[0] ^ 1;
    }
    if(!bit[d]) {
                         
        return dfs1(bit, d-1) + 1 + ( (1<<d) - 1 );
    }
    return dfs2(bit, d-1);
}

int dfs2(int *bit, int d) {
    
    if(d == 0) {
    
        return bit[0];
    }
    if(bit[d]) {
        
        return dfs1(bit, d-1) + 1 + ( (1<<d) - 1 );
    }
    return dfs2(bit, d-1);
}


int minimumOneBitOperations(int n){
    
    if(n == 0) {
    
        return 0;
    }
    int stk[100], top = 0;
    while(n) {
    
        stk[top++] = n & 1;
        n >>= 1;
    } 
    return dfs2(stk, top-1);
}

• $(1)$ int dfs1(int *bit, int d) Express $bit[d:0]\to 1\underset{d}{\underbrace{0...0}}$ The minimum number of steps ;
• $(2)$ int dfs2(int *bit, int d) Express $bit[d:0]\to 0\underset{d}{\underbrace{0...0}}$ The minimum number of steps ;
• $(3)$ For these two functions , Judge bit[d] Whether this bit is consistent with the required bit , If it's not consistent , You need to use rule 2 to flip ; If always , Then continue to calculate $bit[d-1:0]\to 0\underset{d-1}{\underbrace{0...0}}$ The minimum number of steps ;

---

3、 ... and 、 Little knowledge of this topic

   When solving a problem recursively , Abstract out the intermediate steps , It will be much clearer ;

---

Four 、 Instructions for group addition

   I believe most of my articles are 「 College students' 」, Those who can go to college are 「 elite 」, Then we naturally want to 「 Keep improving 」, If you still 「 Freshman 」, So great , You have a lot of time , Of course you can choose 「 binge-watch 」, However ,「 Learn algorithm well 」, Three years later, you will naturally 「 Can't speak in the same day 」.
   So here , I sorted out 「 Dozens of basic algorithms 」 The classification of , Click to open ：

《 Introduction to Algorithms 》
   If the link is blocked , Or there is a permission problem , You can talk to the author in private to solve .

   List of general problem sets ：

   To make it interesting , as well as 「 Take care of beginners 」, At present, the subject only opens the simplest algorithm 「 Enumeration series 」 （ Include ： Linear enumeration 、 Double pointer 、 The prefix and 、 Binary enumeration 、 Three part enumeration ）, When there is Half the members finished painting 「 Enumeration series 」 After all the questions , Will open the next chapter , When this set of questions is finished , You're still in the group , Then you will become 「 In the dead of night 」 The panel of experts A member of the .
   Don't underestimate this panel of experts , After three years, , You will be someone else so far behind that one can only see the dust of the rider ahead The existence of . If you want to join , You can contact me , Considering that everyone is a student , No, 「 The main source of income 」, On your way to God ,「 Won't ask for anything 」.
   Contact the author , Or scan the author's home page QR code and add groups , Join the list of questions

---

Let the world have no algorithm that is difficult to learn
C Language free animation tutorial , Punch in with me ！ 《 In broad daylight C Language 》
Let you form the habit of brushing questions continuously for nine days 《 Nine day training 》
beginner C Summary of language real problems 🧡《C Introduction to language 100 example 》🧡
Group learning , Grow together 《 Algorithm zero basis 100 speak 》
Learn a data structure from a few dynamic diagrams 《 Figure out the data structure 》
Gold Classic graphic tutorial for competitors 《 In the dead of night 》