C++のbitsetを使って数値の2進表現における末尾ゼロの個数を求める方法

本記事では、整数 num を入力として受け取り、C++の bitset を使ってその2進表現における末尾ゼロ（下位ビット側に連続する0）の個数を求める方法を解説します。

bitset は、0と1のビット列を格納するためのコンテナで、いわば「ビットの配列」として扱うことができます。これを利用すると、各ビットに簡単にアクセスして判定を行えます。

入力例と出力例

例1

入力:

num = 10

出力:

Count of number of trailing zeros in Binary representation of a number using Bitset are: 1

解説: 数値10を2進数で表すと「1010」になります。最下位ビットから見て連続する0は1つだけなので、末尾ゼロの個数は1です。

例2

入力:

num = 64

出力:

Count of number of trailing zeros in Binary representation of a number using Bitset are: 6

解説: 数値64を2進数で表すと「1000000」になります。下位6桁がすべて0なので、末尾ゼロの個数は6です。

アルゴリズムの考え方

このアプローチでは bitset を活用します。まず num の値をビット演算子 |= を使って bitset に設定します。その後、forループでビット列を下位ビットから順に走査し、最初に「1」が見つかった時点でループを抜けます。「0」である間はカウントを増やし続けることで、末尾ゼロの個数が求まります。

処理の手順

• 整数 num を入力として受け取ります。
• 関数 trailing_zeroes(int num) は、bitset を用いて2進表現中の末尾ゼロの個数を計算して返します。
• カウント用変数 count を0で初期化します。
• 64ビット分の bitset 変数 arr を宣言します。
• arr |= num により、num のビットパターンを arr に設定します。
• i = 0 から i < 64 までループで走査し、arr[i] が0なら count をインクリメント、1ならループを break します。
• ループ終了後に count を結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int trailing_zeroes(int num){
    int count = 0;
    bitset<64> arr;
    arr |= num;
    for (int i = 0; i < 64; i++){
        if (arr[i] == 0){
            count++;
        } else {
            break;
        }
    }
    return count;
}
int main(){
    int num = 6;
    cout<<"Count of number of trailing zeros in Binary representation of a number using Bitset are: "<<trailing_zeroes(num);
    return 0;
}

実行結果

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

Count of number of trailing zeros in Binary representation of a number using Bitset are: 1

この例では num = 6 であり、6を2進数で表すと「110」なので、末尾ゼロは1つとなります。

まとめ

bitset を使えば、ビット単位の操作を直感的なコードで実装できます。末尾ゼロのカウントは、2進数の性質を理解する良い練習問題であり、ビット演算やシフト演算への理解も深まります。なお、同様の処理は __builtin_ctz 関数などでも実現できますが、bitset を使う方法はロジックが明快で学習用途に適しています。