Tìm giá trị của y mod (2 được nâng lên thành lũy thừa x) trong C ++

Trong bài toán này, chúng ta được cho hai giá trị x và y. Nhiệm vụ của chúng ta là tìm giá trị của y mod (2 được nâng lên thành lũy thừa x) .

Hãy lấy một ví dụ để hiểu vấn đề,

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

Giải thích -

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

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tính trực tiếp giá trị của 2 ^x bằng cách sử dụng hàm pow () và sau đó tìm giá trị của y% 2 ^x .

Một cách tiếp cận khác để giải quyết vấn đề là sử dụng nhật ký. Đối với giá trị của y <2 ^x , phần còn lại là y. Đối với trường hợp này, chúng tôi có

Nhật ký ₂ y

Ngoài ra, giá trị lớn nhất của x có thể là 63, giá trị này sẽ làm tràn giá trị cho y. Do đó, mod bằng x.

Xem xét tất cả những điều này, chúng tôi có ba trường hợp sau -

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

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

The value of y mod 2^x is 909