C++에서 y mod 2^x 값 구하기: 2의 거듭제곱으로 나눈 나머지 계산 방법

문제 소개

이 문제에서는 두 개의 값 x와 y가 주어집니다. 우리의 목표는 y mod 2^x, 즉 y를 2의 x제곱으로 나눈 나머지를 구하는 것입니다.

예시를 통해 문제를 살펴보겠습니다.

입력 : x = 2, y = 19
출력 : 3

설명 −

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

해결 접근 방법

가장 단순한 해결 방법은 pow() 함수를 사용하여 2^x 값을 직접 계산한 뒤, y % 2^x를 구하는 것입니다.

또 다른 효율적인 접근 방식은 로그를 활용하는 것입니다. 만약 y < 2^x라면 나머지는 곧 y 자신이 됩니다. 이 경우 다음 부등식이 성립합니다.

Log₂y < x

한편, x의 최대값은 63까지 허용되며, 그보다 커지면 y 값에서 오버플로우가 발생할 수 있습니다. 따라서 이 경우에도 나머지는 y 그대로 반환됩니다.

이러한 사항들을 모두 종합하면, 해결 로직은 다음 세 가지 경우로 정리할 수 있습니다 −

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<<"y mod 2^x의 값은 "<<findModVal(y, x);
   return 0;
}

실행 결과

y mod 2^x의 값은 909

위 코드에서 주목할 점은 2^x를 pow() 함수 대신 비트 시프트 연산자(1 << x)로 계산했다는 것입니다. 비트 시프트는 거듭제곱 연산보다 속도가 빠르기 때문에, 2의 거듭제곱을 다룰 때 널리 사용되는 최적화 기법입니다. 또한 log2(y) < x 조건을 먼저 검사함으로써 불필요한 나머지 연산을 생략하고, 큰 수에서 발생할 수 있는 오버플로우 위험도 함께 방지할 수 있습니다.