leetcode-342-4的幂

4的幂

题面

leetcode题目 给定一个整数，写一个函数来判断它是否是 \(4\) 的幂次方。如果是，返回 \(true\) ；否则，返回 \(false\) 。

整数 \(n\) 是 \(4\) 的幂次方需满足：存在整数 \(x\) 使得 \(n == 4^x\)

example

输入：n = 16
输出：true

数据范围

\(-2^{31} \leq n \leq 2^{31} - 1\)

题解

总体思路

2的幂中我们可以知道\(n \& (n-1)\) 可以消除掉一个数的最后一位二进制为1的位。
我们观察\(4\)的幂所满足的性质，首先他一定只有一个二进制位为1的位，其次他在三十一个二进制位中出现的位置是一定的。有这两个结论我们呢很容易就能写出代码。

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;

#define _NDEBUG
class Solution
{
    const int MAX = 1 << 30;

public:
    bool isPowerOfFour(int n)
    {
        if (n <= 0 || (n & (n - 1)) != 0)
        {
            return false;
        }
        int mask = 0b1010101010101010101010101010101;
        return (n & mask) != 0;
    }
};

// for test
int main()
{
    Solution s;
    cout << s.isPowerOfFour(16) << endl;
    cout << s.isPowerOfFour(5) << endl;
    cout << s.isPowerOfFour(8) << endl;
    cout << s.isPowerOfFour(1) << endl;
    cout << s.isPowerOfFour(1073741824) << endl;

    return 0;
}