C++で数値のビットを反転する効率的なプログラムの作成方法

この記事では、符号なし整数 n が与えられたとき、その数値のすべてのビットを反転させた結果の数値を返すプログラムを C++ で作成します。

まず、具体例を使って問題を確認しましょう。

入力例

n = 1

出力例

2147483648

解説

1 の2進表現は「000...0001」です。これを反転すると「100...0000」になり、10進数では 2147483648 となります。つまり、最下位ビット(LSB)にあった1が、最上位ビット(MSB)へと移動するイメージです。

方法1: ビット位置の公式を使う方法

最もシンプルな解法は、各ビットの位置を対応付ける公式を利用する方法です。数値の2進表現に対してループ処理を行い、セットされているビット(値が1のビット)の位置を i として検出します。そして、次の公式で反転後の位置を計算します。

((全ビット数) - 1) - i

たとえば32ビット整数の場合、下位から i 番目にあるビットを、上位から i 番目の位置へ移動させることで、ビット列全体を反転できます。

実装コード

#include<iostream>
using namespace std;

unsigned int reverseBitNumber(unsigned int num) {
    unsigned int totalNumberOfBits = sizeof(num) * 8; // 全ビット数(32)
    unsigned int reverseNumber = 0;
    for (int i = 0; i < totalNumberOfBits; i++) {
        // i番目のビットがセットされていれば、反対側の位置にセットする
        if (num & (1 << i))
            reverseNumber |= (1 << ((totalNumberOfBits - 1) - i));
    }
    return reverseNumber;
}

int main() {
    unsigned int n = 21;
    cout << "入力された数値: " << n << endl;
    cout << "ビットを反転した数値: " << reverseBitNumber(n);
    return 0;
}

出力

入力された数値: 21
ビットを反転した数値: 2818572288

21 は2進数で「000...010101」と表されます。これを反転すると「10101000...000」、すなわち 2818572288 になります。

方法2: シフト演算を使う方法

より効率の良いのがシフト演算を利用する方法です。元の数値がゼロになるまで右シフトを繰り返し、そのたびに最下位ビットを結果用の変数へ左シフトしながら格納していきます。ループ終了後、残りのシフト回数分だけ結果を左シフトすれば、32ビット全体の反転が完了します。

この方法の利点は、ループが「有効なビット数」の回数しか実行されない点です。方法1が常に32回ループするのに対し、数値が小さい場合はより少ない処理で済みます。

実装コード

#include<iostream>
using namespace std;

unsigned int reverseBitNumber(unsigned int n) {
    unsigned int remShift = sizeof(n) * 8 - 1; // 残りのシフト回数
    unsigned int reverseNumber = n;
    n >>= 1;
    while (n) {
        reverseNumber <<= 1;
        reverseNumber |= n & 1; // 最下位ビットを結果に追加
        n >>= 1;
        remShift--;
    }
    reverseNumber <<= remShift; // 残りを左シフトして反転完了
    return reverseNumber;
}

int main() {
    unsigned int n = 21;
    cout << "入力された数値: " << n << endl;
    cout << "ビットを反転した数値: " << reverseBitNumber(n);
    return 0;
}

出力

入力された数値: 21
ビットを反転した数値: 2818572288

まとめ

どちらの方法も計算量は O(N)(N はビット数)ですが、方法2は数値の有効ビット数に応じてループ回数が減るため、多くの場合でより高速に動作します。ビット操作は低レベルプログラミングや組み込み開発で頻繁に使われる重要なテクニックなので、ぜひマスターしておきましょう。