C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で最大K個のセットビットを持つX未満の最大数

このチュートリアルでは、与えられたxよりも小さく、最大でk個のセットビットを持つべき最大数を見つけるプログラムを作成します。

問題を解決するための手順を見てみましょう。

  • 数値xとkを初期化します。
  • 数値xのセットビットを見つけます。
  • x-kのセットビット数を繰り返すループを記述します。
    • xの値をx＆（x-1）で更新します。
  • xを返します。

例

コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int largestNumberWithKBits(int x, int k) {
   int set_bit_count = __builtin_popcount(x);
   if (set_bit_count <= k) {
      return x;
   }
   int diff = set_bit_count - k;
   for (int i = 0; i < diff; i++) {
      x &= (x - 1);
   }
   return x;
}
int main() {
   int x = 65, k = 2;
   cout << largestNumberWithKBits(x, k) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

65

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。


  1. 数値に代替パターンのビットがあるかどうかを確認します-C++で1を設定します

    整数nがあるとしましょう。問題は、この整数が2進数に相当する代替パターンを持っているかどうかを確認することです。代替パターンは101010…を意味します。 アプローチは次のようなものです。同等の2進数を使用して各桁をチェックし、2つ連続している場合は偽を返し、そうでない場合は真を返します。 例 #include <iostream> using namespace std; bool hasAlternatePattern(unsigned int n) {    int previous = n % 2;    n = n/2; &nbs

  2. C++で設定されたビット数に従って配列をソートします

    ここでは、セットビットに基づいて配列をソートするための1つの興味深い問題があります。配列内の要素のセットビット数が多い場合、それはセットビット数の少ない別の要素の前に配置されます。いくつかの数が12、15、7であると仮定します。したがって、設定されたビットは、基本的に2進表現の1の数です。これらは、1100（12）、1111（15）、および0111（7）です。したがって、並べ替えると次のようになります- 1111, 0111, 1100 (15, 7, 12) ここでは、最初にセットビットの数を見つける必要があります。次に、C++STLソート関数を使用してそれらをソートします。セットビット数