数値が交互ビットパターンを持つか判定する方法 ― C++でのO(1)アプローチ

はじめに

ある整数 n が与えられたとき、その2進表現が「交互パターン」になっているかどうかを判定する問題を考えてみましょう。ここでいう交互パターンとは、101010… や 0101… のように、1と0が交互に並んでいるビット列のことです。

本記事では、シフト演算とXORを組み合わせることで、定数時間 O(1) でこの判定を行うエレガントな手法を紹介します。

アルゴリズムの考え方

ポイントとなるのは次の計算です。

num = n XOR (n >> 1)

n が交互パターンであれば、隣り合うビット同士は必ず異なる値になります。そこで、n を1ビット右シフトしたものとXORを取ると、各ビット位置で「元のビットと隣のビットの差」が反映され、結果として num のすべてのビットが1 になります。

逆に言えば、「num の全ビットが1であるか」を確認できれば、元の数値が交互パターンを持つかどうかが分かるのです。

全ビットが1かどうかの判定方法

ある数 x の全ビットが1であるかは、次の条件式で O(1) で判定できます。

(x + 1) & x == 0

例えば x = 7（二進数で 111）の場合、x + 1 = 8（1000）となり、111 & 1000 = 0 となります。全ビットが1でない場合は、このAND演算の結果が0にはなりません。

実装例（C++）

#include <iostream>
#include <algorithm>
using namespace std;

// 全ビットが1になっているかを判定する関数
bool isAllBitSet(int n) {
    if (((n + 1) & n) == 0)
        return true;
    return false;
}

// 交互パターンを持つかどうかを判定する関数
bool hasAlternatePattern(unsigned int n) {
    unsigned int num = n ^ (n >> 1);
    return isAllBitSet(num);
}

int main() {
    unsigned int number = 42; // 42 = 101010（2進数）
    if (hasAlternatePattern(number))
        cout << "Has alternating pattern";
    else
        cout << "Has no alternating pattern";
}

出力結果

Has alternating pattern

動作の解説

入力例の 42 は2進数で 101010 です。これを1ビット右シフトすると 010101 になり、両者のXORを取ると 111111 となります。すべてのビットが1なので、この数値は交互パターンを持つと判定されます。

計算量

• 時間計算量： O(1) ― シフト・XOR・ANDといった基本演算のみで構成されており、ビット数に依存しない定数回の操作で完了します。
• 空間計算量： O(1) ― 補助的な変数は定数個のみ使用します。

まとめ

XORと右シフトを組み合わせることで、数値が交互ビットパターン（1010…）を持つかどうかを、ループ処理なしに効率よく判定できます。ビット演算の性質を活かしたテクニックとして、競技プログラミングや組み込み開発の場面でも役立つ知識です。