额，又是一道装逼解法的算法题

chenlei520

"\u003Cdiv\u003E\u003Cp\u003E题目来源于 LeetCode 上第 342 号问题：4 的幂。题目难度为 Easy，目前通过率为 45.3% 。\u003C\u002Fp\u003E\u003Cp\u003E题目描述\u003C\u002Fp\u003E\u003Cp\u003E给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cstrong\u003E示例 1:\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cpre\u003E输入: 16\u003Cbr\u003E输出: true\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003E示例 2:\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cpre\u003E输入: 5\u003Cbr\u003E输出: false\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003E进阶：\u003C\u002Fstrong\u003E你能不使用循环或者递归来完成本题吗？\u003C\u002Fp\u003E\u003Cp\u003E题目解析\u003C\u002Fp\u003E\u003Cp\u003E这道题最直接的方法就是不停的去除以 4 ，看最终结果是否为 1 ，参见代码如下：\u003C\u002Fp\u003E\u003Cpre\u003Eclass Solution {\u003Cbr\u003E public boolean isPowerOfFour(int num) {\u003Cbr\u003E while ( (num != 0) && (num % 4 == 0)) {\u003Cbr\u003E num \u002F= 4;\u003Cbr\u003E }\u003Cbr\u003E return num == 1;\u003Cbr\u003E }\u003Cbr\u003E}\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E不过这段代码使用了 \u003Cstrong\u003E循环\u003C\u002Fstrong\u003E ，逼格不够高。\u003C\u002Fp\u003E\u003Cp\u003E对于一个整数而言，如果这个数是 4 的幂次方，那它必定也是 2 的幂次方。\u003C\u002Fp\u003E\u003Cp\u003E我们先将 2 的幂次方列出来找一下其中哪些数是 4 的幂次方。\u003C\u002Fp\u003E\u003Cp\u003E 十进制 二进制\u003C\u002Fp\u003E\u003Cp\u003E 2\u003C\u002Fp\u003E\u003Cp\u003E 10\u003C\u002Fp\u003E\u003Cp\u003E 4\u003C\u002Fp\u003E\u003Cp\u003E \u003Cstrong\u003E100\u003C\u002Fstrong\u003E （1 在第 3 位）\u003C\u002Fp\u003E\u003Cp\u003E 8\u003C\u002Fp\u003E\u003Cp\u003E 1000\u003C\u002Fp\u003E\u003Cp\u003E 16\u003C\u002Fp\u003E\u003Cp\u003E \u003Cstrong\u003E10000\u003C\u002Fstrong\u003E（1 在第 5 位）\u003C\u002Fp\u003E\u003Cp\u003E 32\u003C\u002Fp\u003E\u003Cp\u003E 100000\u003C\u002Fp\u003E\u003Cp\u003E 64\u003C\u002Fp\u003E\u003Cp\u003E \u003Cstrong\u003E1000000\u003C\u002Fstrong\u003E（1 在第 7 位）\u003C\u002Fp\u003E\u003Cp\u003E 128\u003C\u002Fp\u003E\u003Cp\u003E 10000000\u003C\u002Fp\u003E\u003Cp\u003E 256\u003C\u002Fp\u003E\u003Cp\u003E \u003Cstrong\u003E100000000\u003C\u002Fstrong\u003E（1 在第 9 位）\u003C\u002Fp\u003E\u003Cp\u003E 512\u003C\u002Fp\u003E\u003Cp\u003E 1000000000\u003C\u002Fp\u003E\u003Cp\u003E 1024\u003C\u002Fp\u003E\u003Cp\u003E \u003Cstrong\u003E10000000000\u003C\u002Fstrong\u003E（1 在第 11 位） 找一下规律： 4 的幂次方的数的二进制表示 1 的位置都是在\u003Cstrong\u003E奇数位\u003C\u002Fstrong\u003E。\u003C\u002Fp\u003E\u003Cp\u003E之前在小吴的文章中判断一个是是否是 2 的幂次方数使用的是位运算 n & ( n - 1 )。同样的，这里依旧可以使用位运算：将这个数与特殊的数做位运算。\u003C\u002Fp\u003E\u003Cp\u003E这个特殊的数有如下特点：\u003C\u002Fp\u003E\u003Cul\u003E\u003Cli\u003E足够大，但不能超过 32 位，即最大为 1111111111111111111111111111111（ 31 个 1）\u003C\u002Fli\u003E\u003Cli\u003E它的二进制表示中奇数位为 1 ，偶数位为 0\u003C\u002Fli\u003E\u003C\u002Ful\u003E\u003Cp\u003E符合这两个条件的二进制数是：\u003C\u002Fp\u003E\u003Cpre\u003E1010101010101010101010101010101\u003Cbr\u003E\u003C\u002Fpre\u003E\u003Cp\u003E\u003Cstrong\u003E如果用一个 4 的幂次方数和它做与运算，得到的还是 4 的幂次方数\u003C\u002Fstrong\u003E。\u003C\u002Fp\u003E\u003Cp\u003E将这个二进制数转换成 16 进制表示：0x55555555 。有没有感觉逼格更高点。。。\u003C\u002Fp\u003E\u003Cdiv class=\"pgc-img\"\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002Ff5d0a5b7580b413fbc38b35b1c3c9e99\" img_width=\"892\" img_height=\"579\" alt=\"额，又是一道装逼解法的算法题\" inline=\"0\"\u003E\u003Cp class=\"pgc-img-caption\"\u003E\u003C\u002Fp\u003E\u003C\u002Fdiv\u003E\u003Cp\u003E图片描述\u003C\u002Fp\u003E\u003Cdiv class=\"pgc-img\"\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002Fb689b73f9970462394210bede141a51f\" img_width=\"1024\" img_height=\"768\" alt=\"额，又是一道装逼解法的算法题\" inline=\"0\"\u003E\u003Cp class=\"pgc-img-caption\"\u003E\u003C\u002Fp\u003E\u003C\u002Fdiv\u003E\u003Cp\u003E代码实现\u003C\u002Fp\u003E\u003Cpre\u003Eclass Solution {\u003Cbr\u003E public boolean isPowerOfFour(int num) {\u003Cbr\u003E if (num