C++で数値範囲のビット単位AND（Bitwise AND）を効率的に計算する方法

0 ≤ m ≤ n ≤ 2147483647 を満たす範囲 [m, n] が与えられたとき、この範囲に含まれるすべての整数のビット単位AND（論理積）を求めることを考えます。たとえば、範囲が [5, 7] の場合、5 AND 6 AND 7 = 4 となるため、答えは 4 になります。

アルゴリズムの考え方

範囲内のすべての数値を順番にANDしていくのは非効率です。そこで、m と n の2進表現に注目します。連続する整数同士をANDすると、下位のビットは必ずどこかで 0 になるため、結果として残るのは m と n の共通の上位ビット（共通プレフィックス）だけです。

この性質を利用すると、次の手順で解くことができます。

• カウンタ i を 0 で初期化します。
• m と n が等しくなるまで、両方を1ビット右シフトし、そのたびに i を1ずつ増やします。
• ループ終了後、m を i ビット左シフトして返します。

C++での実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while(m != n){
            m >>= 1;
            n >>= 1;
            i++;
        }
        return m << i;
    }
};
main(){
    Solution ob;
    cout << (ob.rangeBitwiseAnd(5,7));
}

入力

5
7

出力

4

動作の解説

例として [5, 7] の場合を見てみましょう。

• 5 = 101₂、6 = 110₂、7 = 111₂
• 1回目の右シフト後：m = 10₂、n = 11₂（まだ不一致）
• 2回目の右シフト後：m = 1₂、n = 1₂（一致）

ここで i = 2 となっているので、共通プレフィックス「1」を2ビット左に戻すと 100₂ = 4 となり、これが正解です。

このアルゴリズムの計算量は O(log n) であり、範囲内の全数値を走査する O(n) の素朴な実装と比べて大幅に高速です。特に n が大きい場合（最大約21億）でも、最大31回程度のシフト操作で答えが得られます。