C++에서 y mod(2의 거듭제곱 x) 값 찾기

<시간/>

이 문제에서는 두 개의 값 x와 y가 주어집니다. 우리의 임무는 y mod의 값을 찾는 것입니다(2를 x의 거듭제곱으로 올림) .

문제를 이해하기 위해 예를 들어 보겠습니다.

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

설명 -

y % 2^x = 19 % 2² = 19 % 4 = 3

솔루션 접근 방식

문제에 대한 간단한 해결책은 2^x 값을 직접 계산하는 것입니다. pow() 함수를 사용한 다음 y % 2^x 값 찾기 .

문제를 해결하는 또 다른 방법은 로그를 사용하는 것입니다. y <2^x 값의 경우 , 나머지는 y입니다. 이 경우에는

로그₂ y

또한 x의 최대값은 63이 될 수 있으며 y에 대한 값 오버플로가 발생합니다. 따라서 mod는 x와 같습니다.

이 모든 것을 고려하면 다음 세 가지 경우가 있습니다.

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