C++で指定された数値の2進表現における先行ゼロの個数を求める方法

概要

数値が与えられたとき、その2進表現における「先行ゼロ」(最上位の1より手前に並んでいる0)の個数を求めます。ここでは、全体のビット幅を32ビット(unsigned int)と仮定します。

例

入力:

5

出力:

29

5の2進表現は 00000...00101 です。有効なビットは下位3桁のみなので、先行ゼロの個数は 32 − 3 = 29 個となります。

アルゴリズム

• 数値 n を初期化します。
• n の2進表現を求めます。
• 合計ビット数(32)から2進表現の桁数を引きます。
• 結果を返します。

C++での実装

以下は、上記アルゴリズムをC++で実装した例です。

#include <bits/stdc++.h>
using namespace std;

int getLeadingZeroesCount(unsigned int n) {
    int totalBits = sizeof(n) * 8;
    string binary = "";
    while (n) {
        int remainder = n % 2;
        if (remainder || binary.length() > 0) {
            binary += remainder;
        }
        n /= 2;
    }
    return totalBits - binary.length();
}

int main() {
    int n = 101; // 2進表現は 1100101(7桁)
    cout << getLeadingZeroesCount(n) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

25

101(10進数)の2進表現は 1100101 で7桁あるため、32 − 7 = 25 個の先行ゼロが存在します。

補足:組み込み関数を使う方法

GCCやClangでは、__builtin_clz() を使うことで、先行ゼロの個数をループ処理なしで高速に取得できます。

#include <iostream>

int main() {
    unsigned int n = 101;
    std::cout << __builtin_clz(n) << std::endl; // 出力: 25
    return 0;
}

競技プログラミングやパフォーマンスが重要な場面では、この組み込み関数の利用を検討するとよいでしょう。