C++で番号をエンコードする

非負の整数nがあり、そのエンコードされた形式を見つける必要があるとします。エンコード戦略は次のようになります-

したがって、数値が23の場合、結果は1000になり、数値が54の場合、結果は10111になります

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

• binという1つのメソッドを作成します。これには、nとkが必要です。このメソッドは、次のように動作します。
• res：=空の文字列
• while n> 0
  • res：=res + nmod2の数字
  • n：=n / 2
• 数値を逆にする
• whilex>解像度の長さ
  • res：=0の前にresを追加
• return res
• 実際の方法は次のようになります-
• n =0の場合は空の文字列を返し、nが1の場合は「0」を返し、nが2の場合は「1」を返します
• x：=log n base 2
• 2 ^（x + 1）– 1 =nの場合、
  • ans：=空の文字列
  • xを1増やします
  • xが0でない場合、ans：=0にansを追加し、xを1増やします
  • 回答を返す
• return bin（n – 2 ^ x + 1、x）

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string bin(int n, int x){
      string result = "";
      while(n>0){
         result += (n%2) + '0';
         n/=2;
      }
      reverse(result.begin(), result.end());
      while(x>result.size())result = '0' + result;
      return result;
   }
   string encode(int n) {
      if(n == 0)return "";
      if(n == 1)return "0";
      if(n==2) return "1";
      int x = log2(n);
      if(((1<<(x+1)) - 1) == n){
         string ans = "";
         x++;
         while(x--)ans+="0";
         return ans;
      }
      return bin(n - (1<<x) + 1, x);
   }
};
main(){
   Solution ob;
   cout << (ob.encode(23)) << endl;
   cout << (ob.encode(56)) << endl;
}

入力

23
54

出力

1000
11001