Tìm y mod (2^x) trong C++

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

Ví dụ minh họa

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

Giải thích: y % 2^x = 19 % 2^2 = 19 % 4 = 3

Phương pháp giải

Cách đơn giản: tính 2^x bằng hàm pow() rồi lấy y % 2^x.

Cách tối ưu: sử dụng logarit và dịch bit. Có 3 trường hợp:

• Nếu log2(y) < x → trả về y
• Nếu x > 63 → trả về y (tránh tràn số)
• Ngược lại → trả về y % (1 << x)

Ví dụ chương trình

#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 << "Giá trị y mod 2^x là " << findModVal(y, x);
    return 0;
}

Kết quả

Giá trị y mod 2^x là 909