C++で整数のビットが交互パターン（1010…）になっているか判定する方法

整数 n が与えられたとき、その2進表現が「101010…」のように0と1が交互に並ぶパターン（交互パターン）になっているかどうかを判定する方法を紹介します。

基本的なアプローチ

考え方は非常にシンプルです。数値を2進数として下位ビットから順に調べていき、隣り合う2つのビットが同じ値だった時点で false を返します。最後まで隣接ビットが一度も一致しなければ、その数は交互パターンを持っていると判断できます。

1. n % 2 で最下位ビットを取得し、直前のビット（previous）として保存する
2. n / 2 で数値を1ビット右にずらす
3. 新しい最下位ビット（current）と直前のビットを比較する
4. 両者が等しければ false を返す
5. n が 0 になるまで繰り返し、すべてのビットが交互になっていれば true を返す

C++での実装例

#include <iostream>
using namespace std;

// ビットが交互パターン(1010…)になっているか判定する関数
bool hasAlternatePattern(unsigned int n) {
   int previous = n % 2;   // 最下位ビットを記録
   n = n / 2;
   while (n > 0) {
       int current = n % 2;        // 現在の最下位ビット
       if (current == previous)   // 隣接ビットが同じなら交互パターンではない
           return false;
       previous = current;
       n = n / 2;
   }
   return true;
}

int main() {
   unsigned int number = 42;   // 42 = 101010（2進数）
   if (hasAlternatePattern(number))
       cout << "交互パターンを持っています";
   else
       cout << "交互パターンではありません";
}

実行結果

交互パターンを持っています

この例では、42 の2進表現は 101010 であり、0と1が交互に並んでいるため「交互パターンを持っています」と表示されます。一方、例えば 12（2進数で 1100）のような数値は、隣接するビットが同じ箇所があるため false となります。

より効率的なビット演算による方法

ループを使わずに定数時間で判定することも可能です。n と n を1ビット右シフトした値との排他的論理和（XOR）を取ると、交互パターンの数値の場合はすべてのビットが1になります。さらに、その結果 x に対して x & (x + 1) が 0 になれば、x は「111…」という形であることが分かります。

bool hasAlternatePattern(unsigned int n) {
   unsigned int x = n ^ (n >> 1);
   return (x & (x + 1)) == 0;
}

この方法は O(1) の計算量で判定できるため、ビット数が多い大きな数値に対しても高速に動作するという利点があります。