C++で2進数の交互ビットを判定するアルゴリズム

正の整数が与えられたとき、それが交互ビット（alternating bits）を持つかどうかを判定することを考えます。つまり、2進表現において隣り合うどの2つのビットも、必ず異なる値になっている状態です。

例えば、入力が「10」の場合、10の2進表現は「1010」であり、1と0が交互に並んでいるため、出力は True となります。

解法のアプローチ

この問題は、ビット演算を用いて下位ビットから順番に確認していくことで解決できます。手順は以下の通りです。

1. p := n AND 1（n の最下位ビットを p に保存する）
2. n < 2 の場合は true を返す（1桁のビットは自動的に条件を満たすため）
3. n := n / 2（ビットを右に1つシフトする）
4. n が 0 になるまで以下を繰り返す：
   • c := n AND 1（現在の最下位ビットを取得する）
   • c XOR p の結果が 0 の場合、false を返す（同じビットが連続していることを意味する）
   • p := c（比較用のビットを更新する）
   • n := n / 2（右に1つシフトする）
5. ループを抜けたら true を返す

このアルゴリズムでは、XOR 演算を活用しています。隣接する2つのビットが異なれば XOR の結果は 1 になり、同じであれば 0 になるため、結果が 0 になった時点で交互ビットではないと判断できます。計算量は O(log n) と効率的です。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool hasAlternatingBits(int n) {
        bool p = n & 1;
        bool c;
        if(n < 2)
            return true;
        n >>= 1;
        while(n){
            c = n & 1;
            if(c ^ p == 0)
                return false;
            p = c;
            n >>= 1;
        }
        return true;
    }
};
main(){
    Solution ob;
    cout << (ob.hasAlternatingBits(10));
}

入力

10

出力

1

出力が「1」、つまり True を返しており、10（2進数で1010）が交互ビットを持つことが確認できました。