C++の数値の2進表現で長さ>=nの連続する1を検索します

2つの整数xとnがあるとします。このタスクは、nの値以上の1の最初の連続ストリーム（32ビットバイナリ）を検索することです。長さを調整し、その位置を返します。そのような文字列が存在しない場合は、-1を返します。たとえば、x =35、n =2の場合、結果は31になります。32ビット整数での35のバイナリ表現は-

00000000000000000000000000100011。したがって、2つの連続する1がインデックス31に存在するため、答えは31です。

この問題を解決するには、先行ゼロの数を見つける必要があり、その数から、連続する1を見つけようとします。より良いアイデアを得るために例を見てみましょう。

例

#include<iostream>
using namespace std;
int leadingZeroCount(int x) {
   unsigned y;
   int n;
   n = 32;
   for(int i = 16; i > 1; i = i/2 ){
      y = x >> i;
      if(y != 0){
         n -= i;
         x = y;
      }
   }
   y = x >> 1;
   if (y != 0)
      return n - 2;
   return n - x;
}
int consecutiveOnePosition(unsigned x, int n) {
   int k, p;
   p = 0;
   while (x != 0) {
      k = leadingZeroCount(x);
      x = x << k;
      p = p + k;
      k = leadingZeroCount(~x);
      if (k >= n)
         return p + 1;
      x = x << k;
      p = p + k;
   }
   return -1;
}
int main() {
   int x = 35;
   int n = 2;
   cout << "Consecutive 1s of length " << n << " is starting from index: " << consecutiveOnePosition(x, n);
}

出力

Consecutive 1s of length 2 is starting from index: 31