C++で数値の2進表現における最長の連続する1の長さを求めるプログラム

ある整数 n が与えられたとき、その2進表現の中で最も長く連続して現れる「1」の列の長さを求めることを考えます。

例えば、入力が n = 312 の場合を考えてみましょう。312 を2進数で表すと 100111000 となり、ここには「1」が3つ連続した部分が存在するため、出力は 3 となります。

解法のアプローチ

この問題は、ビット演算を使って各ビットを順番に調べていくことで効率的に解くことができます。具体的な手順は以下の通りです。

• 結果を格納する変数 ret と、現在の連続カウントを格納する変数 len をそれぞれ 0 で初期化します。

• i を 0 から 31 まで（32ビット分）ループさせます。

• 各ループ内で (n >> i) & 1 を評価し、i ビット目が 1 であれば len をインクリメントし、0 であれば len を 0 にリセットします。

• 毎回 ret と len の最大値を ret に更新していきます。

• ループ終了後、ret を返します。これが最長の連続する「1」の長さです。

C++による実装例

それでは、上記の手順を実際のC++コードで確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(int n) {
      int ret = 0;
      int len = 0;
      for(int i = 0; i < 32; i++){
         if((n >> i) & 1){
            len++;
         }else{
            len = 0;
         }
         ret = max(ret, len);
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << ob.solve(312);
}

入力

312

出力

3

コードの解説

このアルゴリズムのポイントは、右シフト演算子 >> とビットごとのAND演算 & を組み合わせることで、整数の各ビットを下位から順に取り出せる点です。(n >> i) & 1 は「n の i ビット目が 1 かどうか」を判定する定番のテクニックです。

計算量は32ビット分のループを1回回すだけなので、時間計算量は O(1)（固定回数）、空間計算量も O(1) と非常に効率的です。符号なし整数やより大きなビット幅を扱う場合は、ループ上限を適宜変更することで対応できます。