【C++】最も右側のセットビットの位置を効率的に求めるアルゴリズム

問題概要

この記事では、整数 N が与えられたとき、その数値における最も右側のセットビット（値が 1 になっているビット）の位置（インデックス）を出力する方法を解説します。

問題の例

入力： 4

出力： 3

解説： 4 を 2 進数で表すと「100」となり、セットビットの位置は最下位ビットから数えて 3 番目です。

解き方のアプローチ

単純な解法：シフト操作

最も直感的な方法は、セットビットに行き当たるまで数値を右へシフトし続けることです。しかし、この方法では数値が大きいほど多くのシフト処理が必要になり、計算コストが膨らんでしまいます。

効率的な解法：2の補数とビット演算を活用

より効率的なのが、ブール代数（2 の補数）を利用した手法です。手順は以下の通りです。

1. 数値 N の 2 の補数（-N）を計算します。2 の補数では、最下位のセットビットより下位のビットはそのまま保たれ、それより上位のビットはすべて反転されます。
2. N と -N のビットごとの論理積（AND）を計算します。これにより、最下位のセットビットだけが 1 として残り、他のビットはすべて 0 になります。
3. 得られた数値の log2 を取って 1 を加えると、それが求めるセットビットの位置になります。

計算例

少し複雑に感じるかもしれませんので、実際の数値で確認してみましょう。

N = 10、2進表現 = 1010
-N（2の補数）= 0110
1010 & 0110 = 0010
log2(2) = 1
1 + 1 = 2 … これが求める位置（インデックス）

C++での実装例

上記の解法を実装したプログラムがこちらです。

#include <iostream>
#include <math.h>
using namespace std;

void rightSetBit(int N) {
    int bitIndex = log2(N & -N) + 1;
    cout << bitIndex;
}

int main() {
    int N = 10;
    cout << "数値 " << N << " の最も右側のセットビットの位置 : ";
    rightSetBit(N);
    return 0;
}

出力結果

数値 10 の最も右側のセットビットの位置 : 2

補足

この手法は、数値を 1 ビットずつ調べるループ処理を必要としないため、大きな数値に対しても高速に動作します。なお、GCC や Clang 環境では __builtin_ctz() を使えば、最下位のセットビットより下にある 0 の個数を直接取得できるため、log2 の浮動小数点計算を避けたい場合の代替手段としても有用です。