C++で指定した数値がスパース数かどうかを判定する方法

この記事では、与えられた数値がスパース数（sparse number）であるかどうかを判定する方法を解説します。

スパース数とは？

スパース数とは、その数値を2進数で表したときに、「1」が2つ以上連続して現れない数のことを指します。

例として、数値 72 を考えてみましょう。72を2進数で表すと 01001000 となります。この2進表現には連続する「1」が存在しないため、72はスパース数であるといえます。

判定アルゴリズムの考え方

スパース数の判定は、ビット演算を使うと非常にシンプルに行えます。手順は以下の通りです。

対象の数値を n としたとき、
1. n を右に1ビットシフトします。
2. 元の n との間でビットごとのAND（&）を計算します。
3. 結果が 0 であればスパース数、そうでなければスパース数ではありません。

これは、隣り合うビット同士を比較することで、連続する「1」が存在するかどうかを検出できるためです。もし連続する「1」があれば、n と (n >> 1) の両方で同じ位置に「1」が立ち、ANDの結果が0以外になります。

C++での実装例

#include <iostream>
using namespace std;

bool isSparseNumber(int n) {
    int res = n & (n >> 1);
    if(res == 0)
        return true;
    return false;
}

int main() {
    int num = 72;
    if(isSparseNumber(num)){
        cout << "This is sparse number";
    } else {
        cout << "This is not sparse number";
    }
}

実行結果

This is sparse number

まとめ

このように、右シフトとビットごとのANDを組み合わせることで、O(1) の計算量で数値がスパース数かどうかを効率的に判定できます。ループで各ビットを順番に調べる方法もありますが、ビット演算を活用すればコードも簡潔になり、処理速度の面でも有利です。