C++でymod（2をxに累乗）の値を検索します

この問題では、2つの値xとyが与えられます。私たちのタスクは、 y modの値を見つけることです（2をxに累乗） 。

問題を理解するために例を見てみましょう

Input : x = 2, y = 19
Output : 3

説明 −

y % 2x = 19 % 22 = 19 % 4 = 3

ソリューションアプローチ

この問題の簡単な解決策は、2 ^x の値を直接計算することです。 pow（）関数を使用して、y％2 ^x の値を見つけます 。

この問題を解決する別のアプローチは、ログを使用することです。 y <2 ^x の値の場合 、余りはyです。この場合、

ログ₂ y

また、xの最大値は63で、yの値がオーバーフローする可能性があります。したがって、modはxに等しくなります。

これらすべてを考慮に入れると、次の3つのケースがあります-

if(log y < x) -> return y
else if(x > 63) -> return y
else -> return (y % pow(2, x))

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
long long int findModVal(long long int y, int x){
   if (log2(y) < x)
      return y;
   if (x > 63)
      return y;
   return (y % (1 << x));
}
int main(){
   long long int y = 82829;
   int x = 12;
   cout<<"The value of y mod 2^x is "<<findModVal(y, x);
   return 0;
}

出力

The value of y mod 2^x is 909