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

問題概要

整数が与えられたとき、その数が4の累乗であるかどうかを判定する問題です。

例えば、入力が16であれば、出力はTrueになります。

解決アプローチ

この問題は、ビット演算を活用することで効率的に解くことができます。以下の手順に従って判定を行います。

• num < 0 の場合 → false を返す

• num & (num - 1) の結果が 0 以外の場合 → false を返す

• num & 0x55555555(バイナリ表記で 0101...0101)の結果が 0 の場合 → false を返す

• 上記のチェックすべてを通過した場合 → true を返す

アルゴリズムの解説

num & (num - 1) は、数が2の累乗であるかを判定するための有名なテクニックです。2の累乗はバイナリ表現において1つのビットのみが立ちます。この条件を満たさない数は、この時点で除外されます。

次に、4の累乗は2の累乗の中でも、立っているビットの位置が必ず偶数インデックス(0番目、2番目、4番目…)でなければなりません。そこで、マスク値 0x55555555 とのAND演算を行うことで、ビットが正しい位置にあるかを確認できます。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isPowerOfFour(int num){
        if (num < 0)
            return false;
        if (num & (num - 1))
            return false;
        if (!(num & 0x55555555))
            return false;
        return true;
    }
};
main(){
    Solution ob;
    cout << (ob.isPowerOfFour(64));
}

入力

64

出力

1

まとめ

このアルゴリズムは、ループや再帰を使わずに定数回のビット演算だけで判定できるため、時間計算量 O(1) という非常に効率的な手法です。負の数の除外、2の累乗判定、ビット位置の確認という3段階のチェックで、4の累乗を正確に見分けることができます。