C++で範囲のビット単位AND（&）を求める効率的なアルゴリズム

問題の概要

この問題では、2つの整数値 a と b が与えられ、a から b までの範囲に含まれるすべての数値のビット単位AND（&）を求めることが課題となります。つまり、a & (a+1) & (a+2) & … & (b−1) & b の値を計算する必要があります。

具体的な例で問題を確認してみましょう。

• 入力：a = 3、b = 8
• 出力：0
• 説明：3 & 4 & 5 & 6 & 7 & 8 = 0

シンプルな解法

最も単純なアプローチは、a から開始し、1ずつ値を増加させながら b までのすべての数値に対してビット単位ANDを順番に計算していく方法です。ただし、範囲が広い場合は計算時間が長くなるという欠点があります。

より効率的な解法

ここでは、より少ない計算量で解を求められる効率的なアルゴリズムを紹介します。手順は以下のとおりです。

• ステップ1：b の最下位ビット（LSB）をオフ（0）にします。
• ステップ2：その数値を a と比較し、範囲内に収まっているかどうかを確認します。
  • ステップ2.1：数値がまだ a より大きい場合は、さらにLSBをオフにします。
  • ステップ2.2：数値が a 以下になった場合、その時点の数値が結果となります。

それでは、このアルゴリズムが実際にどのように動作するのか見てみましょう。

例：a = 3、b = 8 の場合

• ステップ1：b = 8（2進数で1000）です。LSBを反転すると、数値は 0000、すなわち 0 になります。
• ステップ2：0 は 3 未満であるため、答えは 0 となります。

このように、範囲内に複数の数値が含まれる場合、下位のビットは必ずどこかで 0 になるため、上位の共通ビット以外はすべて消えていく仕組みです。

サンプルコード

それでは、この問題を解くためのコードを見てみましょう。

#include <stdio.h>
int main(){
    long a, b;
    a = 3; b = 8;
    do{
        b -= (b & -b);
    }while(a < b);
    printf("%li", b);
}

実行結果

0

コードの解説

このコードでは、b & -b という式を使って b の最下位ビット（立っている最下位の1のビット）だけを取り出し、その値を b から減算することでLSBをクリアしています。この操作を b が a 以下になるまで繰り返すことで、範囲内のすべての数値のビット単位ANDをループで全数値を処理することなく効率的に求めることができます。