别人家的面试题：一个整数是否是“4”的N次幂
这是 leetcode.com 的第二篇。与上一篇一样，我们讨论一道相对简单的问题，因为学习总讲究循序渐进。而且，就算是简单的问题，追求算法的极致的话，其中也是有大学问的。
“4”的整数次幂
给定一个32位有符号整数（32 bit signed integer），写一个函数，检查这个整数是否是“4”的N次幂，这里的N是非负整数。
例如：
- 给定 num = 16，返回 true，因为 16 = 4 2
- 给定 num = 5，返回 flase
附加条件：你能够不用循环和递归吗？
解题思路
如果忽略“附加条件”，这题还挺简单的对吧？简直是信手拈来：
版本1
function isPowerOfFour(num){ while(!(num % 4)){ num /= 4; } return num === 1; } 版本1 好像很简单、很强大的样子，它的时间复杂度是 log 4 N。有同学说，还可以做一些微小的改动：
版本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); } 嗯，通过对数公式 log m (n) = log(n) / log(m) 求出指数，然后判断指数是不是一个整数，这样就可以不用循环和递归解决问题。而且，还要注意细节，可以将 log4 当做常量抽取出来，这样不用每次都重复计算，果然是学霸范儿。
不过呢，利用 Math.log 方法也算是某种意义上的犯规吧，有没有不用数学函数，用原生方法来解决呢？
当然有了！而且还不止一种，大家可以继续想30秒，要至少想出一种哦 ——
不用内置函数
这个问题的关键思路和上一道题类似，先考虑“4”的幂的二进制表示：
- 4 0 = 1B
- 4 1 = 100B
- 4 2 = 10000B
- 4 3 = 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，将它拆成 至少两个正数 之和，对拆出的正数求乘积，返回能够得到的 乘积最大的结果 。
想一想你的解法是什么？你能够尽可能减少算法的时间复杂度吗？期待你的答案~~
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
