【C#】整数の2進数表現における最長の連続する「1」の長さを求めるプログラム

整数の2進数表現の中で、最も長く連続している「1」の長さを求めるには、ビットごとの左シフト演算子（Bitwise Left Shift Operator）を使用します。まず、対象となる10進数の値を用意しましょう。

i = (i & (i << 1));

この処理を、変数 i の値が 0 になるまで while ループで繰り返し、別途用意した変数 count を使って繰り返し回数（＝連続する1の長さ）をカウントします。

while (i != 0) {
    i = (i & (i << 1));
    count++;
}

仕組みの解説

このアルゴリズムでは、元の数値と、それを1ビット左にシフトした値との論理積（AND）を計算します。AND演算を行うたびに、連続する「1」の並びが1ビットずつ短くなっていくため、結果が 0 になるまでに実行された回数が、そのまま最長の連続する「1」の個数となります。

ここでは例として、10進数の「150」を取り上げます。

150 の2進数表現は 10010110 です。したがって、この中で最も長く連続している「1」の個数は 2 ということになります。

サンプルコード

using System;
class Demo {
    private static int findConsecutive(int i) {
        int count = 0;
        while (i != 0) {
            i = (i & (i << 1));
            count++;
        }
        return count;
    }

    // ドライバーコード
    public static void Main() {
        // 150 の2進数表現は 10010110
        Console.WriteLine(findConsecutive(150));
    }
}

出力結果

2