C++で数値のK番目のセットビットの位置を求める方法

はじめに

この記事では、2つの整数 N と K が与えられたとき、数 N の2進表現における右から K 番目のセットビット（値が「1」のビット）の位置（インデックス）を求める方法を解説します。

セットビットの確認は、数値を2進表現に変換して行います。インデックスは右端を 0 として数え始め、左へ向かって増加していきます。

たとえば、2進数「011101」の場合、右から 0 番目のインデックスには「1」、1 番目には「0」、というように各ビットが配置されています。

入出力例

• 入力： N = 6, K = 2
• 出力： 2

説明： 6 の2進表現は「0110」です。右から数えて 2 番目のセットビットは、インデックス 2 の位置にあります。

解法のアプローチ

この問題は、ビット演算と右シフトを組み合わせることで効率的に解けます。手順は以下の通りです。

1. 最下位ビットの確認： 現在の最下位ビット（LSB）がセットされているかを N & 1 で判定します。セットされていれば、K の値を 1 減らします。
2. 右シフト： 判定のたびに数値を 1 ビット右へシフト（N >> 1）して次のビットを調べます。同時に、シフトした回数もカウントしておきます。
3. K が 0 になったら終了： K が 0 になった時点でのシフト回数が、求めていた K 番目のセットビットのインデックスです。
4. 見つからない場合： 数値が 0 になっても K が 0 にならなければ、K 番目のセットビットは存在しないため、-1 を返します。

C++による実装例

#include <iostream>
using namespace std;

// 右からK番目のセットビットのインデックスを返す関数
int FindIndexKthBit(int N, int K) {
    int index = 0;
    while (N) {
        // 最下位ビットが1なら、Kをデクリメント
        if (N & 1)
            K--;
        // Kが0になったら、その位置を返す
        if (!K)
            return index;
        index++;
        N = N >> 1;  // 1ビット右シフト
    }
    return -1;  // K番目のセットビットが見つからない場合
}

int main() {
    int N = 12, K = 2;
    cout << "The " << K << "th set bit of the number " << N << " is at index : ";
    int index = FindIndexKthBit(N, K);
    if (index != -1)
        cout << index;
    else
        cout << "\nsorry no index found";
    return 0;
}

出力結果

The 2th set bit of the number 12 is at index : 3

動作の解説

このプログラムでは、N = 12（2進表現では「1100」）、K = 2 としています。処理の流れを追ってみましょう。

• インデックス 0 のビットは「0」（セットされていない）→ シフトして次へ
• インデックス 1 のビットは「0」（セットされていない）→ シフトして次へ
• インデックス 2 のビットは「1」（1 つ目のセットビット）→ K が 2 から 1 に減る
• インデックス 3 のビットは「1」（2 つ目のセットビット）→ K が 0 になり、インデックス 3 を返す

なお、K 番目のセットビットが存在しない場合（たとえば N = 8 で K = 3 の場合など）、関数は -1 を返すため、「該当するビットがない」ことを呼び出し元で適切に判定できます。

計算量

• 時間計算量： O(log N) — N のビット長分だけループするため、桁数に比例します。
• 空間計算量： O(1) — 追加のメモリは不要です。