C++で2進数中の唯一のセットビット（1のビット）の位置を見つける方法

この記事では、2進数表現においてセットビット（値が1になっているビット）が1つだけ存在する整数 N が与えられたとき、その唯一のセットビットの位置を求める方法を解説します。数値にセットビットが1つだけ含まれる場合はその位置を返し、それ以外の場合は「無効な数値」であることを出力します。

具体例で問題を確認してみましょう。

入力

N = 32

出力

6

説明

32 を2進数で表すと「100000」となり、セットビットは6番目（最上位）に1つだけ存在します。

解法のポイント

先に進む前に、押さえておくべき重要な性質があります。それは、「ある数値が2の冪乗であるとき、かつそのときに限り、セットビットはちょうど1つになる」という点です。2の冪乗以外の正の整数には、必ず複数のセットビットが含まれます。このため、まず対象の数値が2の冪乗かどうかを判定し、冪乗であれば位置を求める処理を行う流れになります。

以下では、3つの異なるアプローチを順番に見ていきます。

方法1：最下位ビットから順にチェックする

最もシンプルな方法は、最下位ビット（右端のビット）から順に各ビットの値を調べていくものです。マスク用の変数を左シフトしながらループで判定し、初めてセットビットが見つかった時点の位置を返します。

プログラム例：

#include <iostream>
using namespace std;

bool isPowerOfTwo(unsigned n) {
    if(n > 0) {
        while(n % 2 == 0)
            n /= 2;
        if(n == 1)
            return true;
    }
    return false;
}

int findPositionOfSetBit(unsigned n) {
    unsigned i = 1, position = 1;
    while (!(i & n)) {
        i = i << 1;
        ++position;
    }
    return position;
}

int main(void){
    int n = 64;
    if(!isPowerOfTwo(n))
        cout<<"Invalid Number!";
    else
        cout<<"The position of the number "<<n<<" is "<<findPositionOfSetBit(n);
    return 0;
}

出力

The position of the number 64 is 7

64 は2進数で「1000000」と表されるため、セットビットの位置は7番目となることがわかります。

方法2：右シフトを繰り返す

別のアプローチとして、数値を右シフト演算で0になるまで繰り返しシフトしていく方法があります。0に到達するまでに行ったシフトの回数が、そのままセットビットの位置と一致します。こちらも計算量はビット長に比例する O(log n) です。

プログラム例：

#include <iostream>
using namespace std;

bool isPowerOfTwo(unsigned n) {
    if(n > 0) {
        while(n % 2 == 0)
            n /= 2;
        if(n == 1)
            return true;
    }
    return false;
}

int findPositionOfSetBit(unsigned n) {
    unsigned position = 0;
    while (n) {
        n = n >> 1;
        ++position;
    }
    return position;
}

int main(void){
    int n = 64;
    if(!isPowerOfTwo(n))
        cout<<"Invalid Number!";
    else
        cout<<"The position of the number "<<n<<" is "<<findPositionOfSetBit(n);
    return 0;
}

出力

The position of the number 64 is 7

この方法でも、同じ結果が得られることを確認できます。

方法3：対数（log2）を使った数学的な解法

もう一つの方法は、数学の公式を利用するものです。セットビットが1つしかない数値 n について、次の関係が成り立ちます。

2i = n　※ n は与えられた数値、i はセットビットの位置

したがって、i は次の式で求められます。
i = log2(n)

この方法の利点は、ループ処理が不要になり、O(1) の定数時間で位置を求められる点です。

プログラム例：

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

bool isPowerOfTwo(unsigned n) {
    if(n > 0) {
        while(n % 2 == 0)
            n /= 2;
        if(n == 1)
            return true;
    }
    return false;
}

int findPositionOfSetBit(unsigned n) {
    unsigned position = log2(n) + 1;
    return position;
}

int main(void){
    int n = 64;
    if(!isPowerOfTwo(n))
        cout<<"Invalid Number!";
    else
        cout<<"The position of the number "<<n<<" is "<<findPositionOfSetBit(n);
    return 0;
}

出力

The position of the number 64 is 7

log₂(64) = 6 であるため、+1 を加えた 7 がセットビットの位置として返されます（位置は最下位ビットを1番目として数えます）。

まとめ

本記事では、2進数表現にセットビットが1つだけ含まれる数値に対して、そのビットの位置を求める3つの手法を紹介しました。

• 方法1： マスク変数を左シフトしながらビットを走査する方法（直感的で理解しやすい）
• 方法2： 数値自体を右シフトしていく方法（実装が簡潔）
• 方法3： log₂ を利用する方法（定数時間 O(1) で高速）

いずれの方法でも、事前に数値が2の冪乗かどうかを検証することが重要です。小さな数値であればビット走査でも十分ですが、パフォーマンスを重視する場合は対数を使った方法が有効です。