别人家的面试题：一个整数是否是“4”的N次幂

这是 leetcode.com 的第二篇。与上一篇一样，我们讨论一道相对简单的问题，因为学习总讲究循序渐进。而且，就算是简单的问题，追求算法的极致的话，其中也是有大学问的。

"4"的整数次幂

给定一个32位有符号整数（32 bit signed integer），写一个函数，检查这个整数是否是"4"的N次幂，这里的N是非负整数。

例如：

• 给定 num = 16，返回 true，因为 16 = 42
• 给定 num = 5，返回 flase

附加条件： 你能够不用循环和递归吗？

解题思路

如果忽略"附加条件"，这题还挺简单的对吧？简直是信手拈来：

版本1

function isPowerOfFour(num){
        while(!(num % 4)){
            num /= 4;
        }
        return num === 1;
    }

版本1 好像很简单、很强大的样子，它的时间复杂度是 log4N。有同学说，还可以做一些微小的改动：

版本1.1

function isPowerOfFour(num){
        while(!(num % 4)){
          num >>>= 2;
        }
        return num === 1;
    }

上面的代码用位移替代除法，在其他语言中更快，鉴于 JS 通常情况下非常坑的位运算操作，不一定速度能变快。

好了，最关键的是，不管是 版本1 还是 版本1.1 似乎都不满足我们前面提到的"附加条件"，即不使用循环和递归，或者说，我们需要寻找 O(1) 的解法。

按照惯例，大家先思考10秒钟，然后往下看 ----

不用循环和递归

其实这道题真心有好多种思路，计算指数之类的对数学系学霸们完全不是问题嘛：

版本2

const log4 = Math.log(4);
    function isPowerOfFour(num){
        var n = Math.log(num) / log4;
        return n === (0|n);
    }

嗯，通过对数公式 logm(n) = log(n) / log(m) 求出指数，然后判断指数是不是一个整数，这样就可以不用循环和递归解决问题。而且，还要注意细节，可以将 log4 当做常量抽取出来，这样不用每次都重复计算，果然是学霸范儿。

不过呢，利用 Math.log 方法也算是某种意义上的犯规吧，有没有不用数学函数，用原生方法来解决呢？

当然有了！而且还不止一种，大家可以继续想30秒，要至少想出一种哦 ----

不用内置函数

这个问题的关键思路和上一道题类似，先考虑"4"的幂的二进制表示：

• 40 = 1B
• 41 = 100B
• 42 = 10000B
• 43 = 1000000B
• ……

也就是每个数比上一个数的二进制后面多两个零嘛。最重要的是，"4"的幂的二进制数只有 1 个"1"。如果仔细阅读过上一篇，你就会知道，判断一个二进制数只有 1 个"1"，只需要：

(num & num - 1) === 0

但是，二进制数只有 1 个"1"只是"4"的幂的必要非充分条件，因为"2"的奇数次幂也只有 1 个"1"。所以，我们还需要附加的判断：

(num & num - 1) === 0 && (num & 0xAAAAAAAA) === 0

为什么是 num & 0xAAAAAAAA === 0? 因为这个确保 num 的二进制的那个 "1" 出现在"奇数位"上，也就确保了这个数确实是"4"的幂，而不仅仅只是"2"的幂。

最后，我们得到完整的版本：

版本3

function isPowerOfFour(num) {
        return num > 0 && (num & (num-1)) === 0 
                       && (num & 0xAAAAAAAA) === 0;
    };

上面的代码需要加上 num > 0，是因为 0 要排除在外，否则 (0 & -1) === 0 也是 true

其他版本

上面的版本已经符合了我们的需求，时间复杂度是 O(1)，不用循环和递归。

此外，我们还可以有其他的版本，它们严格来说有的还是"犯规"，但是我们还是可以学习一下这些思路：

版本4：用 Math.sqrt

function isPowerOfFour(num) {
        num = Math.sqrt(num);
        return num > 0 && num === (0|num) && (num & (num-1)) === 0;
    };

版本5：用正则表达式

function isPowerOfFour(num) {
        return /^1(00)*$/g.test(num.toString(2));
    };

以上就是所有的内容，这道题有非常多种思路，相当有趣，也比较考验基本功。如果你有自己的思路，可以留言参与讨论。

下一期我们讨论另外一道题，这道题比这两道题要难一些，但也更有趣：给定一个正整数 n，将它拆成至少两个正整数之和，对拆出的正整数求乘积，返回能够得到的乘积最大的结果。

想一想你的解法是什么？你能够尽可能减少算法的时间复杂度吗？期待你的答案~~