C++で反転・追加操作を繰り返して生成されるバイナリ文字列のk番目のビットを求める方法

初期状態が「0」であるバイナリ文字列 s を考えます。各反復処理では、現在の文字列をビット反転（0と1を入れ替え）し、その結果を元の文字列の末尾に追加していきます。この操作を n 回繰り返した後の文字列から、k 番目のビットを求めるのが本記事のテーマです。

例として、反復回数が 4 回、k = 7 の場合を考えてみましょう。文字列は以下のように変化していきます。

この場合、7 番目のビットは「1」となります。

アルゴリズムの考え方

手順は非常にシンプルです。

1. 現在の文字列の補数（0 を 1 に、1 を 0 に入れ替えたもの）を作成する
2. 補数を元の文字列の末尾に連結する
3. 上記を n 回繰り返す
4. 完成した文字列の k 番目の文字を返す

なお、このようにして生成される文字列は、数学で知られる「トゥー・モース列（Thue–Morse sequence）」と一致することでも有名です。また、文字列の長さは反復ごとに 2 倍になるため、n 回の反復後の長さは 2ⁿ になります。大きな n を扱う場合はメモリ使用量に注意が必要です。

C++での実装例

#include<iostream>
using namespace std;

// 文字列の補数（ビット反転）を求める関数
string getComplement(string bin){
    string temp = "";
    for(int i = 0; i<bin.length(); i++){
        if(bin[i] == '0')
            temp += "1";
        else
            temp += "0";
    }
    return temp;
}

// n回の反復後にk番目の文字を取得する関数
char getCharacter(string bin_str, int n, int k) {
    string res = bin_str;
    for(int i = 0; i<n; i++){
        res += getComplement(res);
    }
    return res[k];
}

int main() {
    int n = 4;
    string bin = "0";
    cout << 7 << "番目の文字は: " << getCharacter(bin, n, 7);
}

実行結果

7番目の文字は: 1

コードの解説

getComplement 関数は、引数として受け取ったバイナリ文字列を走査し、「0」なら「1」を、「1」なら「0」を新しい文字列に追加していくことで補数を生成します。

getCharacter 関数では、まず初期文字列をコピーし、for ループによって n 回の反復処理を実行します。各反復で現在の文字列の補数を末尾に追加していくことで、目的の文字列を構築します。最後に res[k] によって k 番目の文字を返しています。

この実装は直感的で理解しやすい反面、文字列全体を構築するため、n が大きくなるとメモリ消費が指数的に増加します。実用的には、再帰的な性質（前半と後半が互いに補数の関係にある）を利用して、文字列全体を生成せずに k 番目のビットだけを効率的に求める方法もあります。