C++で整数をエンコードするアルゴリズムの実装方法

非負整数 n が与えられたとき、そのエンコード形式を求めることを考えます。エンコードのルールは以下の表の通りです。

表を見ると、1桁の「0」「1」は数値1・2に、2桁の「00」〜「11」は数値3〜6に、3桁の「000」以降は数値7以降に対応していることが分かります。つまり、ビット長ごとに区切られたブロックの中へ、整数が順番に割り当てられていく仕組みです。

たとえば、数値が23であれば結果は「1000」、数値が54であれば「10111」になります。

解き方の手順

この問題を解くには、次の手順に従います。

• まず、n と k を受け取る bin メソッドを作成します。このメソッドは以下のように動作します。
• res := 空文字列
• n > 0 の間、次を繰り返す
  • res := res + （n を 2 で割った余りの数字）
  • n := n / 2
• res を反転する
• x > res の長さ である間、res の先頭に「0」を付け足す
• res を返す

続いて、本体となるメソッドは次の通りです。

• n = 0 なら空文字列を、n = 1 なら「0」を、n = 2 なら「1」を返す
• x := log₂(n)（2を底とした対数）
• もし 2^(x+1) - 1 = n ならば
  • ans := 空文字列
  • x を 1 増やして、x 回だけ ans の末尾に「0」を追加する
  • ans を返す
• それ以外の場合は bin(n - 2^x + 1, x) を返す

ここで、2^(x+1) - 1 という条件は「n + 1 が2のべき乗になっているか」、つまり新しいビット長のブロックの先頭に来ているかどうかを判定しています。該当する場合はすべて「0」の文字列が答えとなり、それ以外の場合はブロック内の位置を2進数に変換して桁数を揃える、という流れです。

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

実装例

#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(54)) << endl;
}

入力

23
54

出力

1000
10111

まとめ

このエンコード方式では、2^k - 1 以上 2^(k+1) - 2 以下の整数が、すべて k 桁の2進文字列へ順に対応付けられます。encode 関数では log₂(n) によって所属ブロックの桁数 x を求め、ブロックの先頭（n = 2^(x+1) - 1）であれば (x+1) 個の「0」を返し、それ以外ではブロック内の位置を表す n - 2^x + 1 を2進変換し、bin 関数で x 桁になるよう先頭を0で埋めた文字列を返します。処理は対数オーダーで完了するため、大きな n に対しても高速に動作するのが特徴です。