C++で与えられた整数が4の累乗かどうかを判定する方法

この問題では、整数 N が与えられ、その整数が4の累乗（べき乗）であるかどうかを判定することが求められます。

問題の例

入力：N = 64
出力：Yes

解説：

43 = 64

64 は 4 を3回掛け合わせた数、つまり4の累乗なので「Yes」が出力されます。

解法のアプローチ

最もシンプルな解き方は、数値を繰り返し4で割っていく方法です。具体的な手順は以下の通りです。

• 数値が0の場合は4の累乗ではないため false を返します。
• 数値が1になるまでループを続け、各段階で4で割り切れるかどうかを確認します。
• 途中で割り切れない場合は false を返します。
• 最終的に1になれば、その数は4の累乗であるため true を返します。

このアルゴリズムの計算量は O(log₄N)、空間計算量は O(1) であり、非常に効率的です。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;

bool isPowerOf4(int n){
   if(n == 0)
      return 0;
   while(n != 1)
   {
      if(n % 4 != 0)
         return 0;
      n = n / 4;
   }
   return 1;
}

int main(){
   int n = 123454;
   if (isPowerOf4(n))
      cout<<"この数は4の累乗です";
   else
      cout<<"この数は4の累乗ではありません";
   return 0;
}

出力結果

この数は4の累乗ではありません

補足：ビット演算を使った別解

より高度な方法として、ビット演算を利用するアプローチもあります。4の累乗は2進数で表すと「1」の後に偶数個の「0」が並ぶ特徴があります。例えば、1（0b1）、4（0b100）、16（0b10000）、64（0b1000000）などです。

これを利用すると、n > 0 && (n & (n-1)) == 0 && (n & 0xAAAAAAAA) == 0 という条件式で、O(1) の定数時間で判定できます。(n & (n-1)) == 0 は2の累乗であることを確認し、(n & 0xAAAAAAAA) == 0 は奇数番目のビットに立っているビットがないこと（つまり4の累乗であること）を確認しています。