Cプログラムで2^X−1の形式の数値を作成する手順を出力する方法

問題の概要

整数 n が与えられたとき、XOR（排他的論理和）演算を利用して、その数値を 2^X − 1 の形式に変換するまでの一連の手順を出力します。

操作のルール

• 奇数番目のステップ： 数値を任意の 2^M − 1（M は自分で選択可能）と XOR 演算します。
• 偶数番目のステップ： 数値を 1 増やします（インクリメント）。

この操作を、n が 2^X − 1 の形式になるまで繰り返し、実行したすべての手順を出力します。なお、最初から n が 2^X − 1 の形になっている場合は、実行すべき手順はありません。

入出力例

入力：22
出力：
    ステップ 1 : 15 と XOR を取る
    ステップ 2 : 1 増やす
    ステップ 3 : 7 と XOR を取る
    ステップ 4 : 1 増やす
    ステップ 5 : 1 と XOR を取る

入力：7
出力：実行すべき手順なし

アルゴリズム

まず、最も左側にある「未セットビット（0 になっているビット）」の位置を求める関数 find_leftmost_unsetbit を用意します。未セットビットが存在しない場合、その数値はすでに 2^X − 1 の形式であることを意味します。

int find_leftmost_unsetbit(int n)
開始
STEP 1 : 変数 ind = -1、i = 1 を宣言して代入
STEP 2 : n が真である間ループ
    もし !(n & 1) ならば、
        ind に i を代入
    条件終了
    i を 1 増やす
    n を 1 ビット右シフト
ループ終了
STEP 3 : ind を返す
終了

void perform_steps(int n)
開始
STEP 1 : left = find_leftmost_unsetbit(n) を宣言・代入
STEP 2 : もし left == -1 ならば、
        「実行すべき手順なし」と表示して戻る
STEP 3 : 変数 step = 1 を宣言・代入
STEP 4 : find_leftmost_unsetbit(n) != -1 である間ループ
    もし step % 2 == 0（偶数ステップ）ならば、
        n を 1 増やし、「Step n : Increase by 1」と表示
    それ以外（奇数ステップ）の場合、
        m = find_leftmost_unsetbit(n)
        num = (pow(2, m) - 1)
        n = n ^ num
        「Step N : Xor with Num」と表示
    step を 1 増やす
ループ終了
終了

C言語での実装例

#include <stdio.h>
#include <math.h>

// 最も左にある未セットビット（0ビット）の位置を求める
int find_leftmost_unsetbit(int n){
    int ind = -1;
    int i = 1;
    while (n) {
        if (!(n & 1))
            ind = i;
        i++;
        n >>= 1;
    }
    return ind;
}

void perform_steps(int n){
    // 最も左の未セットビットを調べる
    int left = find_leftmost_unsetbit(n);
    // 未セットビットが存在しない場合（すでに 2^x - 1 の形式）
    if (left == -1) {
        printf("No Steps to be performed\n");
        return;
    }
    // ステップ数をカウントする変数
    int step = 1;
    // 数値が 2^x - 1 の形式になるまで繰り返す
    while (find_leftmost_unsetbit(n) != -1) {
        // 偶数ステップの場合は 1 増やす
        if (step % 2 == 0) {
            n += 1;
            printf("Step %d: Increase by 1\n", step);
        }
        // 奇数ステップの場合は 2^m - 1 と XOR を取る
        else {
            // 最も左の未セットビットを求める
            int m = find_leftmost_unsetbit(n);
            int num = (int)(pow(2, m) - 1);
            n = n ^ num;
            printf("Step %d : Xor with %d\n", step, num);
        }
        // ステップを進める
        step += 1;
    }
}

int main(){
    int n = 22;
    perform_steps(n);
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

Step 1 : Xor with 15
Step 2 : Increase by 1
Step 3 : Xor with 7
Step 4 : Increase by 1
Step 5 : Xor with 1

動作のポイント

例として n = 22（2進数で 10110）を考えてみます。最も左の未セットビットは上から 4 ビット目なので、まず 2⁴ − 1 = 15 と XOR を取り、下位ビットを反転させます。その後、1 を加えることで桁上がりを利用して残りの未セットビットを解消し、最終的に 11111（= 2⁵ − 1 = 31）へ到達します。このように「XOR で上位の未セットビットを立てる」「+1 で下位を整える」という交互操作により、効率的に 2^X − 1 の形式へ変換できます。