C++で2進数表現におけるk番目のビットの値を求める方法

問題概要

この問題では、2つの整数 n と k が与えられ、n の2進数表現における k 番目のビットの値を求めることが課題となります。

具体例で理解しよう

入力：n = 5, k = 2
出力：0

解説：

5 の2進数表現 = 0101
最下位ビット（LSB）から数えて2番目のビットは 0 です。

解法のアプローチ

この問題は、ビット演算を使うことで効率的に解くことができます。手順は以下の通りです。

1. k 番目のビットだけが 1 になっている数（つまり「1」を (k−1) 回左シフトした値）を作成します。
2. その数と n のビットごとの AND（論理積）を計算します。これにより、k 番目以外のビットはすべて 0 になります。
3. 結果を (k−1) ビット右にシフトすると、k 番目のビットの値（0 または 1）がそのまま得られます。

C++での実装例

以下は、上記の解法を実装した C++ プログラムです。

#include <iostream>
using namespace std;

void findKBitVal(int n, int k){
   cout << ((n & (1 << (k - 1))) >> (k - 1));
}

int main(){
   int n = 29, k = 4;
   cout << "The value of kth bit in binary of the number is ";
   findKBitVal(n, k);
   return 0;
}

出力結果

The value of kth bit in binary of the number is 1

まとめ

ビット演算（AND とシフト）を組み合わせることで、O(1) の時間計算量で任意の位置のビット値を取得できます。このテクニックは、フラグ管理やビットマスク処理など、競技プログラミングやシステム開発のさまざまな場面で応用される基本操作なので、ぜひマスターしておきましょう。