Power of Four trong C++

Kiểm tra số nguyên num có phải là lũy thừa của 4 hay không (4^k).

Ví dụ: 16 → true, 5 → false.

Giải thuật (Bit manipulation)

1. num > 0.
2. num là lũy thừa của 2: (num & (num-1)) == 0.
3. Bit 1 nằm ở vị trí chẵn (0-indexed): (num & 0x55555555) != 0 (mask 0101...).

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555);
    }
};

int main() {
    Solution ob;
    cout << boolalpha << ob.isPowerOfFour(64); // true
    return 0;
}

Đầu vào / Đầu ra

Input: 64
Output: true (1)