Example 28
4的幂
题目概述：是给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
示例 1：
输入：n = 16
输出：true
示例 2：
输入：n = 5
输出：false
示例 3：
输入：n = 1
输出：true
解题思路：如果n 是4 的幂，那么它可以表示成4x的形式，我们可以发现它除以3 的余数一定为1，即：
4x ≡ (3 + 1)x ≡ 1x ≡ 1 (mod 3)
如果n 是2 的幂却不是4 的幂，那么它可以表示成4x×2的形式，此时它除以3 的余数一定为2。
因此可以通过n 除以3 的余数是否为1 来判断n 是否是4 的幂。
判断一个数n是否是2的幂的方法如下：
一个数n 是2 的幂，当且仅当n 是正整数，并且n 的二进制表示中仅包含1 个1。
因此们可以考虑使用位运算，将n 的二进制表示中最低位的那个1 提取出来，再判断剩余的数值是否为0 即可。下面介绍两种常见的与「二进制表示中最低位」相关的位运算方法。
第一个方法是是
n&(n-1)
其中&表示按位与运算。该位运算技巧可以直接将n二进制表示的最低位1移除，它的原理如下：
假设n 的二进制表示为(a10...0)2，其中a 表示若干个高位，1表示最低位的那个1，0...0 表示后面的若干个0，那么n−1 的二进制表示为：
(a01...1)2
将(a10...0)2与(a01⋯1)2进行按位与运算，高位a 不变，在这之后的所有位都会变为0，这样就将最低位的那个1移除了。
因此，如果n 是正整数并且n&(n-1)=0，那么n 就是2 的幂。
第二个方法是
n&(-n)
其中−n是n的相反数，是一个负数。该位运算技巧可以直接获取n二进制表示的最低位的1。
由于负数是按照补码规则在计算机中存储的，−n的二进制表示为n的二进制表示的每一位取反再加上1，因此它的原理如下：
假设n 的二进制表示为(a10⋯0)2，其中a表示若干个高位，1表示最低位的那个1，0...0 表示后面的若干个0，那么−n的二进制表示为：
(a01...1)2+(1)2 = (a10...0)2
其中a表示将a每一位取反。将(a10...1)2与(a10...0)2进行按位与运算，高位全部变为0，最低位的1以及之后的所有0 不变，这样就获取了n二进制表示的最低位的1。
因此，如果n是正整数并且n&(-n)=n，那么n就是2的幂。
解题步骤：
1. 判断是否n大于0且n是2的幂且n除以3的余数为1，并将结果返回。
示例代码如下：
public class PowerOfFour { /** * 是给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。 * 整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x * 示例 1： * <p> * 输入：n = 16 * 输出：true * 示例 2： * 输入：n = 5 * 输出：false * 示例 3： * 输入：n = 1 * 输出：true * 来源：力扣（LeetCode） * 链接：https://leetcode.cn/problems/power-of-four */ public static void main(String[] args) { PowerOfFour pof = new PowerOfFour(); System.out.println(pof.isPowerOfFour(16)); // true } /** * 官方 * @param n * @return */ public boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1; } /** * 个人——修改官方 * @param n * @return */ /*public boolean isPowerOfFour(int n) { return n > 0 && 1073741824 % n == 0 && n % 3 == 1; }*/ /** * 网友-枚举法 * @param n * @return */ /*public boolean isPowerOfFour(int n) { switch (n) { case 1: case 4: case 16: case 262144: case 65536: case 4096: case 1048576: case 4194304: case 16384: case 16777216: case 1024: case 268435456: case 256: case 64: case 67108864: case 1073741824: break; default: return false; } return true; }*/ }
