バイナリ表現の数をC++の1に減らすためのステップ数

バイナリ形式の数sがあるとします。これらのルールの下で1に減らすためのステップ数を見つける必要があります-

• 現在の数が偶数の場合は、2で割る必要があります。

• 現在の数が奇数の場合は、1を追加する必要があります。

したがって、入力が「1101」の場合、「1101」は13であるため、出力は6になります。したがって、13は奇数であり、1を加算して14を取得します。次に、14は偶数であり、2で除算して7を取得します。その7は奇数です。1を足して8を取得します。

次に、8は再び、2で除算して4を取得します。再び4は偶数で、2で除算して2を取得し、最後に2は偶数で、2で除算して1を取得します。

これを解決するには、次の手順に従います-

• 関数addStrings（）を定義します。これは、配列num1、配列num2、

  を取ります。

• 配列retを定義する

• キャリー：=0、合計：=0

• num1とnum2を逆にする

• i：=0、j：=0

• while（i

  • i

    • 合計：=キャリー+（num1 [i] + num2 [j]）

    • retの最後にsummod2を挿入します

    • キャリー：=合計/ 2

    • （iを1増やします）

    • （jを1増やします）

  • それ以外の場合、i

    • 合計：=キャリー+（num1 [i]）

    • retの最後にsummod2を挿入します

    • キャリー：=合計/ 2

    • （iを1増やします）

  • それ以外の場合

    • 合計：=キャリー+（num2 [j]）

    • retの最後にsummod2を挿入します

    • キャリー：=合計/ 2

    • （jを1増やします）

• キャリーがゼロ以外の場合、-

  • retの最後にキャリーを挿入

• i：=retのサイズ

• ans：=空白の文字列

• i> =0の場合、更新（iを1減らします）、実行-

  • ans：=ans +（ret [i] + ASCII of '0'）

• return（ansのサイズが0と同じ場合は「0」、それ以外の場合はans）

• 関数addBinary（）を定義します。これは、配列a、配列b、

  を取ります。

• addStrings（a、b）を返す

• 配列makeVectorを定義し、vからコピーします

  • 配列retを定義する

  • 初期化i：=0の場合、i

    • v[i]を挿入-retの最後に「0」のASCII

  • retを返す

• メインの方法から、次のようにします。

• ret：=0

• 配列x=makeVector from s

  を定義します

• x> 1のサイズで、-

  • （retを1増やします）

  • xの最後の要素が0と同じ場合、-

    • xから最後の要素を削除する

  • それ以外の場合

    • サイズ1のアレイ温度を定義します

    • temp [0]：=1

    • x：=makeVector（addBinary（x、temp））

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string addStrings(vector<int> num1, vector<int> num2){
      vector<int> ret;
      int carry = 0;
      int sum = 0;
      reverse(num1.begin(), num1.end());
      reverse(num2.begin(), num2.end());
      int i = 0;
      int j = 0;
      while (i < num1.size() || j < num2.size()) {
         if (i < num1.size() && j < num2.size()) {
            sum = carry + (num1[i]) + (num2[j]);
            ret.push_back(sum % 2);
            carry = sum / 2;
            i++;
            j++;
         }
         else if (i < num1.size()) {
            sum = carry + (num1[i]);
            ret.push_back(sum % 2);
            carry = sum / 2;
            i++;
         }
         else {
            sum = carry + (num2[j]);
            ret.push_back(sum % 2);
            carry = sum / 2;
            j++;
         }
      }
      if (carry)
         ret.push_back(carry);
      i = ret.size() - 1;
      string ans = "";
      for (; i >= 0; i--)
         ans += (ret[i] + '0');
      return ans.size() == 0 ? "0" : ans;
   }
   string addBinary(vector<int>& a, vector<int>& b){
      return addStrings(a, b);
   }
   vector<int> makeVector(string v){
      vector<int> ret;
      for (int i = 0; i < v.size(); i++)
         ret.push_back(v[i] - '0');
      return ret;
   }
   int numSteps(string s){
      int ret = 0;
      vector<int> x = makeVector(s);
      while (x.size() > 1) {
         ret++;
         if (x.back() == 0) {
            x.pop_back();
         }
         else {
            vector<int> temp(1);
            temp[0] = 1;
            x = makeVector(addBinary(x, temp));
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.numSteps("1101"));
}

入力

"1101"

出力

6