C言語で整数の下位kビットの順番を逆にする方法

C言語で整数nの下位kビットの順番を逆にする方法について解説します。例えば、数値が「00101110」のような場合、これを「01110100」に逆順にするにはどうすればよいのか、効率的な方法を探ります。

1. ビット反転の基本
2. 従来の方法：各ビットを取り出す方法
3. エレガントな方法：ビットシフトとマスクを使った効率的な逆順処理
4. まとめ

1. ビット反転の基本

ビット反転とは、数値の各ビットを反転させる操作です。通常、この操作はビットシフトやマスクを使って行いますが、今回は特に下位kビットの順番を逆にする方法に焦点を当てます。

2. 従来の方法：各ビットを取り出す方法

最も基本的な方法は、整数nの各ビットを1つずつ取り出し、そのビットを新しい位置にセットしていく方法です。この方法では、ビットシフト演算や論理演算子（AND、OR）を駆使して操作します。しかし、この方法はコードが冗長になりがちです。

3. エレガントな方法：ビットシフトとマスクを使った効率的な逆順処理

もっとエレガントな方法は、ビットシフトを使い、マスクを利用して一度に複数ビットを処理することです。例えば、下位kビットだけを取り出し、反転させるためのビットシフトを行うことで、効率的に逆順を実現できます。

以下はその例です。

#include 

unsigned int reverse_bits(unsigned int n, int k) {
    unsigned int reversed = 0;
    for (int i = 0; i < k; i++) {
        reversed = (reversed << 1) | (n & 1);  // 最下位ビットを追加
        n >>= 1;  // ビットシフトして次へ
    }
    return reversed;
}

int main() {
    unsigned int n = 0b00101110;
    int k = 8;
    unsigned int result = reverse_bits(n, k);
    printf("%u\n", result);  // 結果: 01110100
    return 0;
}