C++에서 숫자 인코딩

음이 아닌 정수 n이 있고 인코딩된 형식을 찾아야 한다고 가정합니다. 인코딩 전략은 다음과 같습니다 -

따라서 숫자가 23이면 결과는 1000이 되고 숫자가 54이면 10111이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• bin이라는 메소드를 하나 생성합니다. 이것은 n과 k가 필요하며 이 메소드는 아래와 같이 작동합니다.
• res :=빈 문자열
• n> 0
  동안
  • res :=res + n mod 2의 숫자
  • n :=n /2
• 숫자 역순
• while x> res의 길이
  • res :=res를 앞에 0 추가
• 반환 결과
• 실제 방법은 다음과 같습니다 -
• n =0이면 빈 문자열을 반환하고, n이 1이면 "0"을 반환하고, n이 2이면 "1"을 반환합니다.
• x :=log n 밑수 2
• 2 ^ (x + 1) – 1 =n이면
  • ans :=빈 문자열
  • x 1씩 증가
  • x가 0이 아닌 경우 ans :=ans와 함께 0을 추가하고 x를 1만큼 증가
  • 반환
• 반환 빈(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