C++でBase-2に変換する

数値Nがあるとすると、基数-2（負の2）の値を表す「0」と「1」で構成される文字列を見つける必要があります。文字列が正確に「0」でない限り、返される文字列には先行ゼロが含まれていてはなりません。したがって、入力が2の場合、出力は（-2）^ 2 +（-2）^ 1 +（-2）^ 0=2のように「110」になります。

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

• ret：=空の文字列

• N =0の場合、「0」を返します

• Nが0以外の場合

  • rem：=N mod（– 2）

  • N：=N /（-2）

  • rem <0かつrem：=rem + 2の場合、Nを1増やします

  • ret：=ret + rem as string

• 文字列を逆にするret

• retを返します。

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string baseNeg2(int N) {
      string ret = "";
      if(N == 0) return "0";
      while(N){
         int rem = N % (-2);
         N /= -2;
         if(rem < 0) rem += 2, N++;
         ret += to_string(rem);
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.baseNeg2(17));
}

入力

17

出力

10001