C++で数値に連続するセットビット（隣接する1）があるかどうかを判定する方法

ここでは、ある整数の2進表現の中に「隣接するセットビット」（連続した1）が存在するかどうかを判定する方法を解説します。たとえば、数値12は2進数で「1100」と表され、上位2桁に連続する1が含まれています。

判定の考え方

この判定は、ビットシフトとAND演算（論理積）を組み合わせることで、非常にシンプルに実現できます。手順は以下のとおりです。

1. 対象の数値 n を1ビット右シフトする（n >> 1）。これにより、各ビットがひとつ隣の桁へ移動します。
2. 元の数値 n とシフト後の値との間でビットごとのAND（n & (n >> 1)）を計算します。
3. 計算結果が0以外であれば連続する1が存在し、0であれば存在しません。

右シフトを行うと、元々隣り合っていたビット同士が同じ桁位置で重なります。そのため、隣接する2ビットがどちらも1だった場合にのみ、AND演算の結果に1が残るという仕組みです。

C++での実装例

#include <iostream>
using namespace std;

// 隣接するセットビット（連続する1）を持つかどうかを判定する
bool hasConsecutiveOnes(int n) {
    return (n & (n >> 1)) != 0;
}

int main() {
    int num = 12; // 2進数では 1100
    if (hasConsecutiveOnes(num)) {
        cout << \"連続する1があります\";
    } else {
        cout << \"連続する1はありません\";
    }
    return 0;
}

出力

連続する1があります

動作の確認（num = 12 の場合）

• 12 の2進表現：1100
• 1ビット右シフト：0110（= 6）
• AND演算の結果：1100 & 0110 = 0100（= 4）

結果は4で0ではないため、「12には連続する1が存在する」と正しく判定できています。

逆に、10（2進数で1010）のように1が離れて並んでいる数値では、1010 & 0101 = 0000 となり、「連続する1はない」と判定されます。

注意点

判定条件は必ず「結果が0以外であること」で行ってください。誤って「結果が1と等しいか」で判定してしまうと、連続する1の位置によってAND演算の結果が 1・2・4・8 などさまざまな値になるため、正しく判定できないケースが発生します。

まとめ

n & (n >> 1) を計算し、その結果が0でなければ、その数値は隣接するセットビット（連続する1）を持つと判定できます。この方法は定数時間 O(1) で動作するため非常に効率的で、競技プログラミングや組み込み開発などでも広く使われるテクニックです。なお、符号付き整数の負の値を扱う場合は挙動に注意し、必要に応じて unsigned 型を使用すると安全です。