C++で y mod 2^x（2のx乗）の値を求める方法

この問題では、2つの値 x と y が与えられ、y を 2 の x 乗（2^x）で割った余りの値を求めることが課題となります。

具体例を見て、問題の内容を確認しましょう。

入力 : x = 2, y = 19
出力 : 3

解説 −

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

解法のアプローチ

最もシンプルな解法は、pow() 関数を使って 2^x の値を直接計算し、その後で y % 2^x を求める方法です。

もうひとつの効率的なアプローチとして、対数（log）を活用する方法があります。y < 2x が成り立つ場合、割り算の余りは y 自身と等しくなります。この条件は次のように表せます。

log₂y < x

さらに、long long 型で扱える最大ビット幅を考慮すると、x の最大値は 63 です。x がこれを超えると 2^x はオーバーフローしてしまいますが、この場合 y は必ず 2^x より小さくなるため、余りは y 自身と一致します。

以上を踏まえると、処理は次の3つのケースに分けられます。

if(log2(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