C++で2進数の文字列を1に減らすまでのステップ数を求める方法

問題の概要

2進数形式で与えられた数値 s を、以下のルールに従って 1 になるまで減らしていくとき、必要なステップ数を求めることを考えます。

• 現在の数が偶数の場合：その数を 2 で割る
• 現在の数が奇数の場合：その数に 1 を加える

具体例

入力が "1101" の場合、出力は 6 になります。"1101" は10進数で 13 を表します。処理の流れは以下の通りです。

1. 13 は奇数なので、1 を加えて 14 にする（ステップ1）
2. 14 は偶数なので、2 で割って 7 にする（ステップ2）
3. 7 は奇数なので、1 を加えて 8 にする（ステップ3）
4. 8 は偶数なので、2 で割って 4 にする（ステップ4）
5. 4 は偶数なので、2 で割って 2 にする（ステップ5）
6. 2 は偶数なので、2 で割って 1 にする（ステップ6）

合計 6 ステップで 1 に到達できました。

解法のアプローチ

この問題を解くために、以下の手順でアルゴリズムを構成します。

1. 文字列として2進数を加算する関数 addStrings()

大きな数でも扱えるよう、2進数を配列（各桁の0と1）として保持し、筆算のように桁ごとに加算を行います。繰り上がり（carry）を管理しながら、下位の桁から順に計算していきます。

• 結果を格納する配列 ret を定義する
• carry（繰り上がり）と sum を 0 で初期化する
• 両方の配列を反転し、下位桁から処理できるようにする
• どちらかの配列に未処理の桁がある間、以下を繰り返す
  • 両方の桁が存在する場合：carry + num1[i] + num2[j] を計算し、sum % 2 を ret の末尾に追加、carry を sum / 2 で更新
  • num1 のみ残っている場合：carry + num1[i] を計算して同様に処理
  • num2 のみ残っている場合：carry + num2[j] を計算して同様に処理
• 最後に carry が残っていれば ret に追加する
• ret を逆順にして文字列 ans を組み立てて返す

2. 文字列を整数ベクトルに変換する makeVector()

文字列の各文字から '0' のASCIIコードを引くことで、'0'/'1' の文字を整数 0/1 に変換したベクトルを作成します。

3. メインの処理 numSteps()

• ステップカウンタ ret を 0 で初期化する
• 入力文字列 s をベクトル x に変換する
• x のサイズが 1 より大きい間、以下を繰り返す
  • ret を 1 増やす
  • 最後の要素（最下位ビット）が 0 なら偶数なので、末尾の要素を削除する（2で割る操作に相当）
  • 最後の要素が 1 なら奇数なので、1 を表すベクトル temp を作成し、addBinary() で x に加算する
• 最終的な ret を返す

ポイントは、2進数において「2で割る」操作は単純に末尾のビットを削除するだけで実現できることです。これにより、実際の除算を行わずに効率的に処理できます。

実装例

理解を深めるため、以下のC++による実装を見てみましょう。

#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

まとめ

このアルゴリズムでは、2進数の性質を活かして演算を簡略化しています。偶数の場合の「2で割る」は末尾ビットの削除（O(1)）、奇数の場合の「1を加える」はビット列の加算で処理します。文字列として2進数を扱うことで、非常に長いビット列にも対応できるのが特徴です。計算量は、最悪の場合でもビット長に対して線形時間で収まります。