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

はじめに

このチュートリアルでは、数値のビットを効率的に反転するプログラムについて解説します。

非負の整数が与えられたとき、その数値を2進数形式に変換し、各ビットを反転(0を1に、1を0に)した後、反転結果の10進数の値を出力することを目的とします。

例えば、17は2進数で「10001」と表されます。これを反転すると「01110」となり、10進数では14になります。

アルゴリズムの考え方

ビット反転を効率的に行うには、以下の手順に従います。

1. 最上位ビットの位置を求める: log2(n) を使って、数値 n の最上位ビット(最も左側の1)の位置 x を取得します。
2. マスクを作成する: 1 を x ビット左シフトした値に対して m | (m - 1) を計算することで、最上位ビット以下のすべてのビットが1になったマスクを作成します。
3. XORで反転する: 元の数値とマスクを XOR 演算することで、有効なビット範囲内のすべてのビットを一度に反転できます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

// 数値のビットを反転する関数
int invert_bit(int n){
    int x = log2(n);
    int m = 1 << x;
    m = m | m - 1;
    n = n ^ m;
    return n;
}

int main(){
    int n = 17;
    cout << invert_bit(n) << endl;
    return 0;
}

出力

14

コードの解説

n = 17 の場合の処理の流れを具体的に見てみましょう。

• 17 は2進数で「10001」です。
• log2(17) = 4 なので、最上位ビットの位置は 4 です。
• m = 1 << 4 = 16(2進数で「10000」)
• m = 16 | 15 = 31(2進数で「11111」)
• n = 17 ^ 31 = 14(「10001」^「11111」=「01110」)

このように、XOR演算によって「10001」の各ビットが反転され、「01110」、すなわち10進数の14が得られます。

計算量

このアルゴリズムは log2 の計算とビット演算のみで構成されているため、時間計算量は O(1)、空間計算量も O(1) と非常に効率的です。ループで1ビットずつ反転する方法と比べ、大きな数値でも高速に処理できる点が大きなメリットです。

まとめ

log2 による最上位ビットの検出とビットマスク、XOR演算を組み合わせることで、数値のビット反転を定数時間で実現できます。ビット操作の基礎を理解するのに最適なテクニックなので、ぜひマスターしておきましょう。